Submission #1016859
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; bool a = dfs(x+l); bool b = dfs(x+l-1); u[x] = b; return u[x] = a||b; } 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 | 1000 |
Code Size | 1426 Byte |
Status | AC |
Exec Time | 133 ms |
Memory | 9972 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | Dataset4 | Dataset5 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 100 / 100 | 200 / 200 | 200 / 200 | 400 / 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 | 4 ms | 1152 KB |
subtask_01_02.txt | AC | 4 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 | 4 ms | 1152 KB |
subtask_01_08.txt | AC | 4 ms | 1152 KB |
subtask_01_09.txt | AC | 4 ms | 1152 KB |
subtask_01_10.txt | AC | 4 ms | 1152 KB |
subtask_01_11.txt | AC | 4 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 | 4 ms | 1152 KB |
subtask_01_15.txt | AC | 4 ms | 1152 KB |
subtask_01_16.txt | AC | 4 ms | 1152 KB |
subtask_01_17.txt | AC | 4 ms | 1152 KB |
subtask_02_01.txt | AC | 4 ms | 1152 KB |
subtask_02_02.txt | AC | 4 ms | 1152 KB |
subtask_02_03.txt | AC | 4 ms | 1152 KB |
subtask_02_04.txt | AC | 4 ms | 1152 KB |
subtask_02_05.txt | AC | 4 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 | 4 ms | 1152 KB |
subtask_02_13.txt | AC | 4 ms | 1152 KB |
subtask_02_14.txt | AC | 4 ms | 1152 KB |
subtask_02_ex1.txt | AC | 4 ms | 1152 KB |
subtask_03_01.txt | AC | 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 | 4 ms | 1152 KB |
subtask_03_06.txt | AC | 4 ms | 1152 KB |
subtask_03_07.txt | AC | 4 ms | 1152 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 | AC | 4 ms | 1152 KB |
subtask_03_14.txt | AC | 4 ms | 1152 KB |
subtask_03_15.txt | AC | 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 | 1280 KB |
subtask_04_02.txt | AC | 5 ms | 1280 KB |
subtask_04_03.txt | AC | 5 ms | 1280 KB |
subtask_04_04.txt | AC | 5 ms | 1280 KB |
subtask_04_05.txt | AC | 5 ms | 1280 KB |
subtask_04_06.txt | AC | 5 ms | 1280 KB |
subtask_04_07.txt | AC | 5 ms | 1280 KB |
subtask_04_08.txt | AC | 4 ms | 1152 KB |
subtask_04_09.txt | AC | 4 ms | 1152 KB |
subtask_04_10.txt | AC | 5 ms | 1280 KB |
subtask_04_11.txt | AC | 5 ms | 1280 KB |
subtask_04_12.txt | AC | 5 ms | 1280 KB |
subtask_04_13.txt | AC | 4 ms | 1152 KB |
subtask_04_14.txt | AC | 4 ms | 1152 KB |
subtask_04_15.txt | AC | 4 ms | 1152 KB |
subtask_05_01.txt | AC | 133 ms | 8436 KB |
subtask_05_02.txt | AC | 122 ms | 8436 KB |
subtask_05_03.txt | AC | 122 ms | 9972 KB |
subtask_05_04.txt | AC | 90 ms | 8436 KB |
subtask_05_05.txt | AC | 77 ms | 7924 KB |
subtask_05_06.txt | AC | 75 ms | 7668 KB |
subtask_05_07.txt | AC | 74 ms | 7540 KB |
subtask_05_08.txt | AC | 7 ms | 1408 KB |
subtask_05_09.txt | AC | 7 ms | 1408 KB |
subtask_05_10.txt | AC | 66 ms | 7668 KB |
subtask_05_11.txt | AC | 59 ms | 7668 KB |
subtask_05_12.txt | AC | 61 ms | 7668 KB |
subtask_05_13.txt | AC | 49 ms | 5624 KB |
subtask_05_14.txt | AC | 65 ms | 6772 KB |
subtask_05_15.txt | AC | 30 ms | 3704 KB |