Submission #1007649
Source Code Expand
#include <string> #include <vector> #include <iostream> #include <algorithm> using namespace std; class SuffixArray { void CEB(vector<int> &v, vector<int> &b) { int vs = v.size(), bs = b.size(); fill(b.begin(), b.end(), 0); for (int i = 0; i < vs; i++) b[v[i]]++; for (int i = 1; i < bs; i++) b[i] += b[i - 1]; } void ISort(vector<int> &v, vector<int> &SA, int mv, vector<int> &b, vector<int> &isL) { int vs = v.size(), bs = b.size(); fill(b.begin(), b.end(), 0); for (int i = 0; i < vs; i++) b[v[i]]++; int sum = 0; for (int i = 0; i < bs; i++) b[i] += sum, swap(sum, b[i]); for (int i = 0; i < vs; i++) { if (SA[i] > 0 && isL[SA[i] - 1]) SA[b[v[SA[i] - 1]]++] = SA[i] - 1; } } void IISort(vector<int> &v, vector<int> &SA, int mv, vector<int> &b, vector<int> &isL) { CEB(v, b); for (int i = v.size() - 1; i >= 0; i--) { if (SA[i] > 0 && !isL[SA[i] - 1]) SA[--b[v[SA[i] - 1]]] = SA[i] - 1; } } vector<int>SA_IS(vector<int> v, int mv) { int vs = v.size(); if (vs == 1) return vector<int>(1, 0); vector<int> isL(vs), b(mv + 1), SA(vs, -1), ord(vs); auto isLMS = [&](int x)->bool { return x > 0 && isL[x - 1] && !isL[x]; }; for (int i = vs - 2; i >= 0; i--) isL[i] = (v[i] > v[i + 1]) || (v[i] == v[i + 1] && isL[i + 1]); CEB(v, b); for (int i = 0; i < vs; i++) { if (isLMS(i)) SA[--b[v[i]]] = i; } ISort(v, SA, mv, b, isL); IISort(v, SA, mv, b, isL); int cur = 0; for (int i = 0; i < vs; i++) { if (isLMS(i)) ord[i] = cur++; } vector<int> nxv(cur); cur = -1; int prev = -1; for (int i = 0; i < vs; i++) { if (!isLMS(SA[i])) continue; bool diff = false; for (int d = 0; d < vs; d++) { if (prev == -1 || v[SA[i] + d] != v[prev + d] || isL[SA[i] + d] != isL[prev + d]) { diff = true; break; } else if (d && isLMS(SA[i] + d))break; } if (diff) cur++, prev = SA[i]; nxv[ord[SA[i]]] = cur; } vector<int> reord(nxv.size()); for (int i = 0; i < vs; i++) { if (isLMS(i)) reord[ord[i]] = i; } vector<int> nxSA = SA_IS(nxv, cur); CEB(v, b); for (int i = 0; i < SA.size(); i++) SA[i] = -1; for (int i = nxSA.size() - 1; i >= 0; i--) { SA[--b[v[reord[nxSA[i]]]]] = reord[nxSA[i]]; } ISort(v, SA, mv, b, isL); IISort(v, SA, mv, b, isL); return SA; } vector<int>SA_IS(string s) { vector<int> v(s.size() + 1); for (int i = 0; i < s.size(); i++) v[i] = s[i] + 1; return SA_IS(v, *max_element(v.begin(), v.end())); } vector<int>construct_lcp(string &s, vector<int> &sa) { vector<int> lcp(s.size()), rank(s.size() + 1); int n = s.size(), h = 0; for (int i = 0; i <= n; i++) rank[sa[i]] = i; for (int i = 0; i < n; i++) { int j = sa[rank[i] - 1]; if (h) h--; for (; j + h < n && i + h < n; h++) { if (s[j + h] != s[i + h]) break; } lcp[rank[i] - 1] = h; } return lcp; } public: string s; vector<int> sa, lcp; void init(string &T) { s = T; sa = SA_IS(s); lcp = construct_lcp(s, sa); } SuffixArray(string &t) { init(t); } SuffixArray() {} bool contain(string &t) { int a = 0, b = s.size(); while (b - a > 1) { int c = (a + b) / 2; if (s.compare(sa[c], t.size(), t) < 0) a = c; else b = c; } return !s.compare(sa[b], t.size(), t); } }; string s; int n, x; int main() { cin >> x >> s; n = s.size(); SuffixArray Q(s); vector<int> sa = Q.sa; vector<int> sa_inverse(n + 1); for (int i = 0; i < n + 1; i++) sa_inverse[sa[i]] = i; int l = 0, r = n + 2, quot = n / (x + 1); while (r - l > 1) { int m = (l + r) / 2; vector<int> dp(n + 1, 999999999); dp[0] = 0; for (int i = quot; i <= n; i++) { dp[i] = min(dp[i], dp[i - quot] + 1); if (sa_inverse[i] < m && i > quot) dp[i] = min(dp[i], dp[i - quot - 1] + 1); } if (dp[n] == x + 1) r = m; else l = m; } cout << s.substr(sa[l], quot + 1) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | square1001 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3963 Byte |
Status | WA |
Exec Time | 134 ms |
Memory | 3584 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | Dataset4 | Dataset5 | ||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | WA | 3 ms | 256 KB |
subtask_01_02.txt | WA | 3 ms | 256 KB |
subtask_01_03.txt | WA | 3 ms | 256 KB |
subtask_01_04.txt | WA | 3 ms | 256 KB |
subtask_01_05.txt | WA | 3 ms | 256 KB |
subtask_01_06.txt | WA | 3 ms | 256 KB |
subtask_01_07.txt | WA | 3 ms | 256 KB |
subtask_01_08.txt | WA | 3 ms | 256 KB |
subtask_01_09.txt | WA | 3 ms | 256 KB |
subtask_01_10.txt | WA | 3 ms | 256 KB |
subtask_01_11.txt | WA | 3 ms | 256 KB |
subtask_01_12.txt | WA | 3 ms | 256 KB |
subtask_01_13.txt | WA | 3 ms | 256 KB |
subtask_01_14.txt | WA | 3 ms | 256 KB |
subtask_01_15.txt | WA | 3 ms | 256 KB |
subtask_01_16.txt | WA | 3 ms | 256 KB |
subtask_01_17.txt | WA | 3 ms | 256 KB |
subtask_02_01.txt | WA | 3 ms | 256 KB |
subtask_02_02.txt | WA | 3 ms | 256 KB |
subtask_02_03.txt | WA | 3 ms | 256 KB |
subtask_02_04.txt | WA | 3 ms | 256 KB |
subtask_02_05.txt | AC | 3 ms | 256 KB |
subtask_02_06.txt | WA | 3 ms | 256 KB |
subtask_02_07.txt | WA | 3 ms | 256 KB |
subtask_02_08.txt | WA | 3 ms | 256 KB |
subtask_02_09.txt | WA | 3 ms | 256 KB |
subtask_02_10.txt | WA | 3 ms | 256 KB |
subtask_02_11.txt | WA | 3 ms | 256 KB |
subtask_02_12.txt | WA | 3 ms | 256 KB |
subtask_02_13.txt | WA | 3 ms | 256 KB |
subtask_02_14.txt | WA | 3 ms | 256 KB |
subtask_02_ex1.txt | AC | 3 ms | 256 KB |
subtask_03_01.txt | WA | 3 ms | 256 KB |
subtask_03_02.txt | WA | 3 ms | 256 KB |
subtask_03_03.txt | WA | 3 ms | 256 KB |
subtask_03_04.txt | WA | 3 ms | 256 KB |
subtask_03_05.txt | AC | 3 ms | 256 KB |
subtask_03_06.txt | WA | 3 ms | 256 KB |
subtask_03_07.txt | WA | 3 ms | 256 KB |
subtask_03_08.txt | WA | 3 ms | 256 KB |
subtask_03_09.txt | WA | 3 ms | 256 KB |
subtask_03_10.txt | AC | 3 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 | WA | 3 ms | 256 KB |
subtask_03_14.txt | WA | 3 ms | 256 KB |
subtask_03_15.txt | RE | 112 ms | 384 KB |
subtask_03_ex2.txt | WA | 3 ms | 256 KB |
subtask_03_ex3.txt | AC | 3 ms | 256 KB |
subtask_04_01.txt | WA | 3 ms | 256 KB |
subtask_04_02.txt | WA | 3 ms | 256 KB |
subtask_04_03.txt | WA | 3 ms | 256 KB |
subtask_04_04.txt | WA | 3 ms | 256 KB |
subtask_04_05.txt | AC | 3 ms | 256 KB |
subtask_04_06.txt | WA | 3 ms | 256 KB |
subtask_04_07.txt | WA | 3 ms | 256 KB |
subtask_04_08.txt | WA | 3 ms | 256 KB |
subtask_04_09.txt | WA | 3 ms | 256 KB |
subtask_04_10.txt | WA | 3 ms | 256 KB |
subtask_04_11.txt | AC | 3 ms | 256 KB |
subtask_04_12.txt | AC | 3 ms | 256 KB |
subtask_04_13.txt | WA | 3 ms | 256 KB |
subtask_04_14.txt | WA | 3 ms | 256 KB |
subtask_04_15.txt | WA | 3 ms | 256 KB |
subtask_05_01.txt | WA | 30 ms | 3584 KB |
subtask_05_02.txt | WA | 30 ms | 3584 KB |
subtask_05_03.txt | WA | 30 ms | 3584 KB |
subtask_05_04.txt | WA | 28 ms | 3584 KB |
subtask_05_05.txt | AC | 28 ms | 3584 KB |
subtask_05_06.txt | WA | 27 ms | 3584 KB |
subtask_05_07.txt | WA | 27 ms | 3584 KB |
subtask_05_08.txt | WA | 25 ms | 3584 KB |
subtask_05_09.txt | WA | 23 ms | 3584 KB |
subtask_05_10.txt | AC | 27 ms | 3328 KB |
subtask_05_11.txt | AC | 19 ms | 2432 KB |
subtask_05_12.txt | AC | 19 ms | 2432 KB |
subtask_05_13.txt | WA | 21 ms | 2816 KB |
subtask_05_14.txt | RE | 134 ms | 3328 KB |
subtask_05_15.txt | RE | 120 ms | 1664 KB |