Submission #1291541
Source Code Expand
#include <bits/stdc++.h> using namespace std; struct SuffixArray { vector< int > SA; string s; void Build_SA(const string &str) { s = str; SA.resize(s.size()); iota(begin(SA), end(SA), 0); sort(begin(SA), end(SA), [&](const int &a, const int &b) { if(s[a] == s[b]) return (a > b); return (s[a] < s[b]); }); vector< int > classes(s.size()), c(s.size()), cnt(s.size()); for(int i = 0; i < s.size(); i++) { c[i] = s[i]; } for(int len = 1; len < s.size(); len <<= 1) { for(int i = 0; i < s.size(); i++) { if(i > 0 && c[SA[i - 1]] == c[SA[i]] && SA[i - 1] + len < s.size() && c[SA[i - 1] + len / 2] == c[SA[i] + len / 2]) { classes[SA[i]] = classes[SA[i - 1]]; } else { classes[SA[i]] = i; } } iota(begin(cnt), end(cnt), 0); copy(begin(SA), end(SA), begin(c)); for(int i = 0; i < s.size(); i++) { int s1 = c[i] - len; if(s1 >= 0) SA[cnt[classes[s1]]++] = s1; } classes.swap(c); } } int operator[](int k) const { return (SA[k]); } int size() const { return (s.size()); } bool lt_substr(string &t, int si = 0, int ti = 0) { int sn = s.size(), tn = t.size(); while(si < sn && ti < tn) { if(s[si] < t[ti]) return (true); if(s[si] > t[ti]) return (false); ++si, ++ti; } return (si >= sn && ti < tn); } int lower_bound(string &t) { int low = -1, high = SA.size(); while(high - low > 1) { int mid = (low + high) >> 1; if(lt_substr(t, SA[mid])) low = mid; else high = mid; } return (high); } pair< int, int > lower_upper_bound(string &t) { int idx = lower_bound(t); int low = idx - 1, high = SA.size(); t.back()++; while(high - low > 1) { int mid = (low + high) >> 1; if(lt_substr(t, SA[mid])) low = mid; else high = mid; } t.back()--; return (make_pair(idx, high)); } void output() { for(int i = 0; i < size(); i++) { cout << i << ": " << s.substr(SA[i]) << endl; } } }; int main() { int K; string S; cin >> K; cin >> S; SuffixArray sa; sa.Build_SA(S); //sa.output(); int L = (S.size() + K) / (K + 1); vector< int > rev(S.size()); for(int i = 0; i < S.size(); i++) rev[sa[i]] = i; auto check = [&](int v) { int ret = 0; for(int i = 0; i < S.size(); ++ret) { int add = rev[i] < v ? L : L - 1; if(add == 0) return (false); i += add; } return (ret <= K + 1); }; int low = 0, high = sa.size(); while(high - low > 1) { int mid = (low + high) >> 1; if(check(mid)) high = mid; else low = mid; } cout << S.substr(sa[low], L) << endl; }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | ei13333 |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2887 Byte |
Status | AC |
Exec Time | 49 ms |
Memory | 2048 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 | 1 ms | 256 KB |
subtask_01_02.txt | AC | 1 ms | 256 KB |
subtask_01_03.txt | AC | 1 ms | 256 KB |
subtask_01_04.txt | AC | 1 ms | 256 KB |
subtask_01_05.txt | AC | 1 ms | 256 KB |
subtask_01_06.txt | AC | 1 ms | 256 KB |
subtask_01_07.txt | AC | 1 ms | 256 KB |
subtask_01_08.txt | AC | 1 ms | 256 KB |
subtask_01_09.txt | AC | 1 ms | 256 KB |
subtask_01_10.txt | AC | 1 ms | 256 KB |
subtask_01_11.txt | AC | 1 ms | 256 KB |
subtask_01_12.txt | AC | 1 ms | 256 KB |
subtask_01_13.txt | AC | 1 ms | 256 KB |
subtask_01_14.txt | AC | 1 ms | 256 KB |
subtask_01_15.txt | AC | 1 ms | 256 KB |
subtask_01_16.txt | AC | 1 ms | 256 KB |
subtask_01_17.txt | AC | 1 ms | 256 KB |
subtask_02_01.txt | AC | 1 ms | 256 KB |
subtask_02_02.txt | AC | 1 ms | 256 KB |
subtask_02_03.txt | AC | 1 ms | 256 KB |
subtask_02_04.txt | AC | 1 ms | 256 KB |
subtask_02_05.txt | AC | 1 ms | 256 KB |
subtask_02_06.txt | AC | 1 ms | 256 KB |
subtask_02_07.txt | AC | 1 ms | 256 KB |
subtask_02_08.txt | AC | 1 ms | 256 KB |
subtask_02_09.txt | AC | 1 ms | 256 KB |
subtask_02_10.txt | AC | 1 ms | 256 KB |
subtask_02_11.txt | AC | 1 ms | 256 KB |
subtask_02_12.txt | AC | 1 ms | 256 KB |
subtask_02_13.txt | AC | 1 ms | 256 KB |
subtask_02_14.txt | AC | 1 ms | 256 KB |
subtask_02_ex1.txt | AC | 1 ms | 256 KB |
subtask_03_01.txt | AC | 1 ms | 256 KB |
subtask_03_02.txt | AC | 1 ms | 256 KB |
subtask_03_03.txt | AC | 1 ms | 256 KB |
subtask_03_04.txt | AC | 1 ms | 256 KB |
subtask_03_05.txt | AC | 1 ms | 256 KB |
subtask_03_06.txt | AC | 1 ms | 256 KB |
subtask_03_07.txt | AC | 1 ms | 256 KB |
subtask_03_08.txt | AC | 1 ms | 256 KB |
subtask_03_09.txt | AC | 1 ms | 256 KB |
subtask_03_10.txt | AC | 1 ms | 256 KB |
subtask_03_11.txt | AC | 1 ms | 256 KB |
subtask_03_12.txt | AC | 1 ms | 256 KB |
subtask_03_13.txt | AC | 1 ms | 256 KB |
subtask_03_14.txt | AC | 1 ms | 256 KB |
subtask_03_15.txt | AC | 1 ms | 256 KB |
subtask_03_ex2.txt | AC | 1 ms | 256 KB |
subtask_03_ex3.txt | AC | 1 ms | 256 KB |
subtask_04_01.txt | AC | 2 ms | 256 KB |
subtask_04_02.txt | AC | 2 ms | 256 KB |
subtask_04_03.txt | AC | 2 ms | 256 KB |
subtask_04_04.txt | AC | 2 ms | 256 KB |
subtask_04_05.txt | AC | 2 ms | 256 KB |
subtask_04_06.txt | AC | 2 ms | 256 KB |
subtask_04_07.txt | AC | 2 ms | 256 KB |
subtask_04_08.txt | AC | 2 ms | 256 KB |
subtask_04_09.txt | AC | 2 ms | 256 KB |
subtask_04_10.txt | AC | 2 ms | 256 KB |
subtask_04_11.txt | AC | 2 ms | 256 KB |
subtask_04_12.txt | AC | 1 ms | 256 KB |
subtask_04_13.txt | AC | 1 ms | 256 KB |
subtask_04_14.txt | AC | 1 ms | 256 KB |
subtask_04_15.txt | AC | 1 ms | 256 KB |
subtask_05_01.txt | AC | 49 ms | 2048 KB |
subtask_05_02.txt | AC | 48 ms | 2048 KB |
subtask_05_03.txt | AC | 44 ms | 2048 KB |
subtask_05_04.txt | AC | 46 ms | 2048 KB |
subtask_05_05.txt | AC | 45 ms | 2048 KB |
subtask_05_06.txt | AC | 45 ms | 2048 KB |
subtask_05_07.txt | AC | 44 ms | 2048 KB |
subtask_05_08.txt | AC | 43 ms | 2048 KB |
subtask_05_09.txt | AC | 43 ms | 2048 KB |
subtask_05_10.txt | AC | 40 ms | 2048 KB |
subtask_05_11.txt | AC | 27 ms | 2048 KB |
subtask_05_12.txt | AC | 20 ms | 2048 KB |
subtask_05_13.txt | AC | 32 ms | 1664 KB |
subtask_05_14.txt | AC | 40 ms | 1920 KB |
subtask_05_15.txt | AC | 16 ms | 1024 KB |