Submission #1013706
Source Code Expand
#include <cstdio> #include <cstring> #include <vector> #include <string> #include <algorithm> using namespace std; string s; char s_[111111]; int k; struct SA { string s; vector<int> sa, pos; int gap; void build(const string& s_) { s = s_; sa.resize(s.size()); pos.resize(s.size()); auto comp = [&](int a, int b) { if (pos[a] != pos[b]) return pos[a] < pos[b]; a += gap; b += gap; return (a < int(s.size()) && b < int(s.size())) ? pos[a] < pos[b] : a > b; }; for (size_t i = 0; i < s.size(); i++) { sa[i] = i; pos[i] = s[i]; } vector<int> t(s.size()); for (gap = 1;; gap *= 2) { sort(sa.begin(), sa.end(), comp); for (size_t i = 0; i+1 < s.size(); i++) { t[i+1] = t[i] + (comp(sa[i], sa[i+1]) ? 1 : 0); } for (size_t i = 0; i < s.size(); i++) { pos[sa[i]] = t[i]; } if (t.back() == int(s.size())-1) break; } } }; SA sa; vector<int> vs; int l; bool test(int j) { int c = 0; string buf = ""; string t = s.substr(j, l); // printf("%s\n", t.c_str()); for (size_t i = 0; i < s.size(); i++) { // printf("%zd: %d %d\n", i, x, c); // printf("%zd: %s %d\n", i, buf.c_str(), c); if (l == 1) { if (s[i] > t[0]) return false; } if (((buf+s[i] > t && buf.size()+1 == t.size()) || buf.size()+1 > t.size())) { buf = s[i]; ++c; } else { buf += s[i]; } } return c <= k; } int main(void) { scanf("%d%s", &k, s_); s = s_; sa.build(s); l = (s.size()+k)/(k+1); for (int i = 0; i < int(sa.sa.size()); i++) { if (sa.sa[i]+l <= int(s.size())) { vs.push_back(sa.sa[i]); } } int lb = -1; int rb = vs.size()-1; while (rb-lb > 1) { int mb = (lb+rb)/2; if (test(vs[mb])) { rb = mb; } else { lb = mb; } } printf("%s\n", s.substr(vs[rb], l).c_str()); return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | roxion1377 |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2018 Byte |
Status | AC |
Exec Time | 2108 ms |
Memory | 2168 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:73:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%s", &k, s_); s = s_; ^
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 | 2 ms | 256 KB |
subtask_01_02.txt | AC | 2 ms | 256 KB |
subtask_01_03.txt | AC | 2 ms | 256 KB |
subtask_01_04.txt | AC | 2 ms | 256 KB |
subtask_01_05.txt | AC | 2 ms | 256 KB |
subtask_01_06.txt | AC | 2 ms | 256 KB |
subtask_01_07.txt | AC | 2 ms | 256 KB |
subtask_01_08.txt | AC | 2 ms | 256 KB |
subtask_01_09.txt | AC | 2 ms | 256 KB |
subtask_01_10.txt | AC | 2 ms | 256 KB |
subtask_01_11.txt | AC | 2 ms | 256 KB |
subtask_01_12.txt | AC | 2 ms | 256 KB |
subtask_01_13.txt | AC | 2 ms | 256 KB |
subtask_01_14.txt | AC | 2 ms | 256 KB |
subtask_01_15.txt | AC | 2 ms | 256 KB |
subtask_01_16.txt | AC | 2 ms | 256 KB |
subtask_01_17.txt | AC | 2 ms | 256 KB |
subtask_02_01.txt | AC | 2 ms | 256 KB |
subtask_02_02.txt | AC | 2 ms | 256 KB |
subtask_02_03.txt | AC | 2 ms | 256 KB |
subtask_02_04.txt | AC | 2 ms | 256 KB |
subtask_02_05.txt | AC | 2 ms | 256 KB |
subtask_02_06.txt | AC | 2 ms | 256 KB |
subtask_02_07.txt | AC | 2 ms | 256 KB |
subtask_02_08.txt | AC | 2 ms | 256 KB |
subtask_02_09.txt | AC | 2 ms | 256 KB |
subtask_02_10.txt | AC | 2 ms | 256 KB |
subtask_02_11.txt | AC | 2 ms | 256 KB |
subtask_02_12.txt | AC | 2 ms | 256 KB |
subtask_02_13.txt | AC | 2 ms | 256 KB |
subtask_02_14.txt | AC | 2 ms | 256 KB |
subtask_02_ex1.txt | AC | 2 ms | 256 KB |
subtask_03_01.txt | AC | 2 ms | 256 KB |
subtask_03_02.txt | AC | 3 ms | 256 KB |
subtask_03_03.txt | AC | 2 ms | 256 KB |
subtask_03_04.txt | AC | 3 ms | 256 KB |
subtask_03_05.txt | AC | 3 ms | 256 KB |
subtask_03_06.txt | AC | 2 ms | 256 KB |
subtask_03_07.txt | AC | 2 ms | 256 KB |
subtask_03_08.txt | AC | 3 ms | 256 KB |
subtask_03_09.txt | AC | 2 ms | 256 KB |
subtask_03_10.txt | AC | 2 ms | 256 KB |
subtask_03_11.txt | AC | 3 ms | 256 KB |
subtask_03_12.txt | AC | 3 ms | 256 KB |
subtask_03_13.txt | AC | 2 ms | 256 KB |
subtask_03_14.txt | AC | 2 ms | 256 KB |
subtask_03_15.txt | AC | 2 ms | 256 KB |
subtask_03_ex2.txt | AC | 2 ms | 256 KB |
subtask_03_ex3.txt | AC | 3 ms | 256 KB |
subtask_04_01.txt | AC | 4 ms | 256 KB |
subtask_04_02.txt | AC | 5 ms | 256 KB |
subtask_04_03.txt | AC | 4 ms | 256 KB |
subtask_04_04.txt | AC | 4 ms | 256 KB |
subtask_04_05.txt | AC | 4 ms | 256 KB |
subtask_04_06.txt | AC | 5 ms | 256 KB |
subtask_04_07.txt | AC | 5 ms | 256 KB |
subtask_04_08.txt | AC | 5 ms | 256 KB |
subtask_04_09.txt | AC | 3 ms | 256 KB |
subtask_04_10.txt | AC | 5 ms | 256 KB |
subtask_04_11.txt | AC | 5 ms | 256 KB |
subtask_04_12.txt | AC | 5 ms | 256 KB |
subtask_04_13.txt | AC | 3 ms | 256 KB |
subtask_04_14.txt | AC | 3 ms | 256 KB |
subtask_04_15.txt | AC | 3 ms | 256 KB |
subtask_05_01.txt | AC | 155 ms | 2168 KB |
subtask_05_02.txt | AC | 157 ms | 2168 KB |
subtask_05_03.txt | AC | 95 ms | 2168 KB |
subtask_05_04.txt | AC | 144 ms | 2168 KB |
subtask_05_05.txt | AC | 155 ms | 2168 KB |
subtask_05_06.txt | AC | 156 ms | 2168 KB |
subtask_05_07.txt | AC | 165 ms | 2168 KB |
subtask_05_08.txt | AC | 2108 ms | 1784 KB |
subtask_05_09.txt | AC | 31 ms | 1664 KB |
subtask_05_10.txt | AC | 163 ms | 2168 KB |
subtask_05_11.txt | AC | 196 ms | 2168 KB |
subtask_05_12.txt | AC | 196 ms | 2168 KB |
subtask_05_13.txt | AC | 121 ms | 1752 KB |
subtask_05_14.txt | AC | 157 ms | 2068 KB |
subtask_05_15.txt | AC | 62 ms | 1116 KB |