Submission #1007126
Source Code Expand
#include <iostream> #include <fstream> #include <set> #include <map> #include <string> #include <vector> #include <bitset> #include <algorithm> #include <cstring> #include <cstdlib> #include <cmath> #include <cassert> #include <queue> #define mp make_pair #define pb push_back typedef long long ll; typedef long double ld; using namespace std; const int MX = 220000; int n; char s[MX]; int cc[MX]; int p[MX]; int p2[MX]; int c[MX]; int c2[MX]; int en[MX]; int ans[MX]; int nm(int a, int b) { if (a < 0) return a + b; if (a >= b) return a - b; return a; } void sa() { n += 1; for (int i = 0; i < n; ++i) c[i] = s[i]; for (int i = 0; i < n; ++i) ++cc[c[i] + 1]; for (int i = 1; i < MX; ++i) cc[i] += cc[i - 1]; for (int i = 0; i < n; ++i) p[cc[c[i]]++] = i; for (int k = 0; (1 << k) < n; ++k) { for (int i = 0; i < n; ++i) p[i] = nm(p[i] - (1 << k), n); memset(cc, 0, sizeof(cc)); for (int i = 0; i < n; ++i) ++cc[c[i] + 1]; for (int i = 1; i < MX; ++i) cc[i] += cc[i - 1]; for (int i = 0; i < n; ++i) p2[cc[c[p[i]]]++] = p[i]; memcpy(p, p2, sizeof(p)); int now = 0; c2[p[0]] = 0; for (int i = 1; i < n; ++i) { if (c[p[i]] == c[p[i - 1]] && c[nm(p[i] + (1 << k), n)] == c[nm(p[i - 1] + (1 << k), n)]) c2[p[i]] = now; else c2[p[i]] = ++now; } memcpy(c, c2, sizeof(c)); if (now + 1 >= n) break; } n -= 1; } int l; int k; int check(int x) { memset(en, 0, sizeof(en)); for (int i = 0; i <= x; ++i) { if (p[i] + l <= n) en[p[i]] = 1; } for (int i = 0; i <= n; ++i) ans[i] = 1e9; ans[0] = 0; for (int i = 0; i < n; ++i) { if (l && i + (l - 1) <= n) ans[i + l - 1] = min(ans[i + l - 1], ans[i] + 1); if (en[i] && i + l <= n) ans[i + l] = min(ans[i + l], ans[i] + 1); } if (ans[n] <= k) return 1; else return 0; } int main() { scanf("%d", &k); scanf(" %s", s); n = strlen(s); sa(); ++k; l = (n + k - 1) / k; int lb = 0; int rb = n; while (rb - lb > 1) { int mid = (lb + rb) >> 1; if (check(mid)) rb = mid; else lb = mid; } int st = p[rb]; for (int i = 0; i < l; ++i) cout << s[st + i]; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | LHiC |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2256 Byte |
Status | AC |
Exec Time | 38 ms |
Memory | 5120 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:103:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &k); ^ ./Main.cpp:104:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf(" %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 | 8 ms | 3712 KB |
subtask_01_02.txt | AC | 8 ms | 3712 KB |
subtask_01_03.txt | AC | 8 ms | 3712 KB |
subtask_01_04.txt | AC | 8 ms | 3712 KB |
subtask_01_05.txt | AC | 8 ms | 3712 KB |
subtask_01_06.txt | AC | 8 ms | 3712 KB |
subtask_01_07.txt | AC | 8 ms | 3712 KB |
subtask_01_08.txt | AC | 8 ms | 3712 KB |
subtask_01_09.txt | AC | 8 ms | 3712 KB |
subtask_01_10.txt | AC | 9 ms | 3712 KB |
subtask_01_11.txt | AC | 8 ms | 3712 KB |
subtask_01_12.txt | AC | 8 ms | 3712 KB |
subtask_01_13.txt | AC | 8 ms | 3712 KB |
subtask_01_14.txt | AC | 7 ms | 2816 KB |
subtask_01_15.txt | AC | 8 ms | 3712 KB |
subtask_01_16.txt | AC | 8 ms | 3712 KB |
subtask_01_17.txt | AC | 7 ms | 2816 KB |
subtask_02_01.txt | AC | 9 ms | 3712 KB |
subtask_02_02.txt | AC | 9 ms | 3712 KB |
subtask_02_03.txt | AC | 8 ms | 3712 KB |
subtask_02_04.txt | AC | 8 ms | 3712 KB |
subtask_02_05.txt | AC | 8 ms | 3712 KB |
subtask_02_06.txt | AC | 9 ms | 3712 KB |
subtask_02_07.txt | AC | 9 ms | 3712 KB |
subtask_02_08.txt | AC | 9 ms | 3712 KB |
subtask_02_09.txt | AC | 8 ms | 3712 KB |
subtask_02_10.txt | AC | 10 ms | 3712 KB |
subtask_02_11.txt | AC | 10 ms | 3712 KB |
subtask_02_12.txt | AC | 10 ms | 3712 KB |
subtask_02_13.txt | AC | 9 ms | 3712 KB |
subtask_02_14.txt | AC | 8 ms | 3712 KB |
subtask_02_ex1.txt | AC | 9 ms | 3712 KB |
subtask_03_01.txt | AC | 10 ms | 3712 KB |
subtask_03_02.txt | AC | 10 ms | 3712 KB |
subtask_03_03.txt | AC | 10 ms | 3712 KB |
subtask_03_04.txt | AC | 9 ms | 3712 KB |
subtask_03_05.txt | AC | 10 ms | 3712 KB |
subtask_03_06.txt | AC | 9 ms | 3712 KB |
subtask_03_07.txt | AC | 9 ms | 3712 KB |
subtask_03_08.txt | AC | 9 ms | 3712 KB |
subtask_03_09.txt | AC | 9 ms | 3712 KB |
subtask_03_10.txt | AC | 11 ms | 3712 KB |
subtask_03_11.txt | AC | 11 ms | 3712 KB |
subtask_03_12.txt | AC | 11 ms | 3712 KB |
subtask_03_13.txt | AC | 9 ms | 3712 KB |
subtask_03_14.txt | AC | 10 ms | 3712 KB |
subtask_03_15.txt | AC | 9 ms | 3712 KB |
subtask_03_ex2.txt | AC | 9 ms | 3712 KB |
subtask_03_ex3.txt | AC | 11 ms | 3712 KB |
subtask_04_01.txt | AC | 11 ms | 3712 KB |
subtask_04_02.txt | AC | 10 ms | 3712 KB |
subtask_04_03.txt | AC | 11 ms | 3712 KB |
subtask_04_04.txt | AC | 10 ms | 3712 KB |
subtask_04_05.txt | AC | 10 ms | 3712 KB |
subtask_04_06.txt | AC | 10 ms | 3712 KB |
subtask_04_07.txt | AC | 10 ms | 3712 KB |
subtask_04_08.txt | AC | 10 ms | 3712 KB |
subtask_04_09.txt | AC | 10 ms | 3712 KB |
subtask_04_10.txt | AC | 12 ms | 3712 KB |
subtask_04_11.txt | AC | 15 ms | 3712 KB |
subtask_04_12.txt | AC | 14 ms | 3712 KB |
subtask_04_13.txt | AC | 10 ms | 3712 KB |
subtask_04_14.txt | AC | 10 ms | 3712 KB |
subtask_04_15.txt | AC | 10 ms | 3712 KB |
subtask_05_01.txt | AC | 25 ms | 4992 KB |
subtask_05_02.txt | AC | 27 ms | 4992 KB |
subtask_05_03.txt | AC | 33 ms | 4992 KB |
subtask_05_04.txt | AC | 29 ms | 4992 KB |
subtask_05_05.txt | AC | 29 ms | 4992 KB |
subtask_05_06.txt | AC | 29 ms | 4992 KB |
subtask_05_07.txt | AC | 28 ms | 4992 KB |
subtask_05_08.txt | AC | 29 ms | 4992 KB |
subtask_05_09.txt | AC | 24 ms | 5120 KB |
subtask_05_10.txt | AC | 30 ms | 4992 KB |
subtask_05_11.txt | AC | 37 ms | 4992 KB |
subtask_05_12.txt | AC | 38 ms | 4992 KB |
subtask_05_13.txt | AC | 22 ms | 4608 KB |
subtask_05_14.txt | AC | 27 ms | 4864 KB |
subtask_05_15.txt | AC | 18 ms | 4224 KB |