Submission #1016851
Source Code Expand
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <map> using namespace std; typedef long long ll; int k; string s; int l; vector<string> v; string vv[111111]; bool ch(string x){ int p = 0; for(int i = 0; i < k+1; i++){ if(p+l > (int)s.size()) return true; if(x >= s.substr(p,l)){ p += l; }else{ p += l-1; } } return p == (int)s.size(); } bool u[111111]; bool uv[111111]; bool dfs(int x){ if(x > (int)s.size()) return false; if(x == (int)s.size()) return true; if(uv[x]) return u[x]; uv[x] = true; if(dfs(x+l) || dfs(x+l-1)){ u[x] = true; } return u[x]; } int main(void){ cin >> k >> s; if(k == 0){ cout << s << endl; return 0; } l = (s.size()+k)/(k+1); dfs(0); for(int i = 0; i+l-1 < (int)s.size(); i++){ if(u[i]) v.push_back(s.substr(i,l)); } sort(v.begin(),v.end()); /* cout << "vs " << v.size() << endl; for(int i = 0; i < (int)v.size(); i++) cout << v[i] << endl; */ int lb = -1; int ub = v.size()-1; while(ub-lb > 1){ int mid = (lb+ub)/2; /* cout << lb << " " << ub << endl; cout << "mid " << v[mid] << endl; //*/ if(ch(v[mid])){ ub = mid; }else{ lb = mid; } } cout << v[ub] << endl; }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | gotto |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1410 Byte |
Status | WA |
Exec Time | 118 ms |
Memory | 9972 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | Dataset4 | Dataset5 | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 0 / 100 | 0 / 200 | 0 / 200 | 0 / 400 | ||||||||||||||||||||||
Status |
|
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask_02_ex1.txt, subtask_03_ex2.txt, subtask_03_ex3.txt |
Dataset1 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt |
Dataset2 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt |
Dataset3 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt |
Dataset4 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt |
Dataset5 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt, subtask_05_01.txt, subtask_05_02.txt, subtask_05_03.txt, subtask_05_04.txt, subtask_05_05.txt, subtask_05_06.txt, subtask_05_07.txt, subtask_05_08.txt, subtask_05_09.txt, subtask_05_10.txt, subtask_05_11.txt, subtask_05_12.txt, subtask_05_13.txt, subtask_05_14.txt, subtask_05_15.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask_01_01.txt | AC | 3 ms | 1152 KB |
subtask_01_02.txt | AC | 3 ms | 1152 KB |
subtask_01_03.txt | AC | 4 ms | 1152 KB |
subtask_01_04.txt | AC | 4 ms | 1152 KB |
subtask_01_05.txt | AC | 4 ms | 1152 KB |
subtask_01_06.txt | AC | 4 ms | 1152 KB |
subtask_01_07.txt | AC | 3 ms | 1152 KB |
subtask_01_08.txt | AC | 4 ms | 1152 KB |
subtask_01_09.txt | AC | 3 ms | 1152 KB |
subtask_01_10.txt | AC | 3 ms | 1152 KB |
subtask_01_11.txt | AC | 3 ms | 1152 KB |
subtask_01_12.txt | AC | 4 ms | 1152 KB |
subtask_01_13.txt | AC | 4 ms | 1152 KB |
subtask_01_14.txt | AC | 3 ms | 1152 KB |
subtask_01_15.txt | AC | 3 ms | 1152 KB |
subtask_01_16.txt | AC | 3 ms | 1152 KB |
subtask_01_17.txt | AC | 3 ms | 1152 KB |
subtask_02_01.txt | AC | 4 ms | 1152 KB |
subtask_02_02.txt | AC | 3 ms | 1152 KB |
subtask_02_03.txt | AC | 3 ms | 1152 KB |
subtask_02_04.txt | AC | 3 ms | 1152 KB |
subtask_02_05.txt | WA | 3 ms | 1152 KB |
subtask_02_06.txt | AC | 4 ms | 1152 KB |
subtask_02_07.txt | AC | 4 ms | 1152 KB |
subtask_02_08.txt | AC | 4 ms | 1152 KB |
subtask_02_09.txt | AC | 4 ms | 1152 KB |
subtask_02_10.txt | AC | 4 ms | 1152 KB |
subtask_02_11.txt | AC | 4 ms | 1152 KB |
subtask_02_12.txt | AC | 3 ms | 1152 KB |
subtask_02_13.txt | AC | 4 ms | 1152 KB |
subtask_02_14.txt | AC | 3 ms | 1152 KB |
subtask_02_ex1.txt | WA | 3 ms | 1152 KB |
subtask_03_01.txt | WA | 4 ms | 1152 KB |
subtask_03_02.txt | AC | 4 ms | 1152 KB |
subtask_03_03.txt | AC | 4 ms | 1152 KB |
subtask_03_04.txt | AC | 4 ms | 1152 KB |
subtask_03_05.txt | AC | 3 ms | 1152 KB |
subtask_03_06.txt | AC | 3 ms | 1152 KB |
subtask_03_07.txt | AC | 4 ms | 1280 KB |
subtask_03_08.txt | AC | 4 ms | 1152 KB |
subtask_03_09.txt | AC | 4 ms | 1152 KB |
subtask_03_10.txt | AC | 4 ms | 1152 KB |
subtask_03_11.txt | AC | 4 ms | 1152 KB |
subtask_03_12.txt | AC | 4 ms | 1152 KB |
subtask_03_13.txt | WA | 4 ms | 1152 KB |
subtask_03_14.txt | WA | 4 ms | 1152 KB |
subtask_03_15.txt | WA | 4 ms | 1152 KB |
subtask_03_ex2.txt | AC | 4 ms | 1152 KB |
subtask_03_ex3.txt | AC | 4 ms | 1152 KB |
subtask_04_01.txt | AC | 5 ms | 1152 KB |
subtask_04_02.txt | WA | 4 ms | 1152 KB |
subtask_04_03.txt | AC | 5 ms | 1280 KB |
subtask_04_04.txt | AC | 4 ms | 1152 KB |
subtask_04_05.txt | AC | 4 ms | 1152 KB |
subtask_04_06.txt | AC | 4 ms | 1152 KB |
subtask_04_07.txt | AC | 4 ms | 1152 KB |
subtask_04_08.txt | AC | 4 ms | 1152 KB |
subtask_04_09.txt | AC | 3 ms | 1152 KB |
subtask_04_10.txt | AC | 4 ms | 1152 KB |
subtask_04_11.txt | AC | 4 ms | 1152 KB |
subtask_04_12.txt | AC | 4 ms | 1152 KB |
subtask_04_13.txt | WA | 3 ms | 1152 KB |
subtask_04_14.txt | AC | 4 ms | 1152 KB |
subtask_04_15.txt | WA | 4 ms | 1152 KB |
subtask_05_01.txt | AC | 102 ms | 5752 KB |
subtask_05_02.txt | AC | 96 ms | 5752 KB |
subtask_05_03.txt | AC | 118 ms | 9972 KB |
subtask_05_04.txt | AC | 66 ms | 5752 KB |
subtask_05_05.txt | AC | 47 ms | 4476 KB |
subtask_05_06.txt | AC | 39 ms | 3580 KB |
subtask_05_07.txt | AC | 33 ms | 3196 KB |
subtask_05_08.txt | AC | 7 ms | 1408 KB |
subtask_05_09.txt | AC | 7 ms | 1408 KB |
subtask_05_10.txt | AC | 38 ms | 3580 KB |
subtask_05_11.txt | AC | 35 ms | 3580 KB |
subtask_05_12.txt | AC | 35 ms | 3580 KB |
subtask_05_13.txt | WA | 14 ms | 1920 KB |
subtask_05_14.txt | WA | 17 ms | 2176 KB |
subtask_05_15.txt | WA | 13 ms | 1792 KB |