Submission #1003157
Source Code Expand
#include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef long long int ll; typedef vector<int> VI; typedef vector<ll> VL; typedef pair<int, int> PI; const ll mod = 1e9 + 7; const int K = 20; /* * Suffix Array. * Required Headers: algorithm, cassert, string, vector * Verified by: http://arc050.contest.atcoder.jp/submissions/818745 * Reference: http://mayokoex.hatenablog.com/entry/2016/04/03/145845 */ struct compare_sa { const std::vector<int> &rank; int n, k; compare_sa(const std::vector<int> &rank, int n, int k) : rank(rank), n(n), k(k) {} bool operator () (int i, int j) { if (rank[i] != rank[j]) { return rank[i] < rank[j]; } int ri = i + k <= n ? rank[i + k] : -1; int rj = j + k <= n ? rank[j + k] : -1; return ri < rj; } }; std::vector<int> create_sa(const std::string& s) { int n = s.length(); std::vector<int> sa(n + 1, -1); std::vector<int> rank(n + 1, -1); std::vector<int> tmp(n + 1, -1); for (int i = 0; i <= n; ++i) { sa[i] = i; rank[i] = i < n ? s[i] : -1; } for (int k = 1; k <= n; k *= 2) { compare_sa cp = compare_sa(rank, n, k); std::sort(sa.begin(), sa.begin() + n + 1, cp); tmp[sa[0]] = 0; for (int i = 1; i <= n; ++i) { tmp[sa[i]] = tmp[sa[i - 1]] + (cp(sa[i - 1], sa[i]) ? 1 : 0); } for (int i = 0; i <= n; ++i) { rank[i] = tmp[i]; } } return sa; } std::vector<int> create_lcp(const std::string &s, const std::vector<int> &sa) { int n = s.length(); std::vector<int> rank(n + 1); std::vector<int> lcp(n, -1); for (int i = 0; i <= n; ++i) { rank[sa[i]] = i; } int h = 0; lcp[0] = 0; for (int i = 0; i < n; ++i) { int j = sa[rank[i] - 1]; h = std::max(0, h - 1); for (; j + h < n && i + h < n; ++h) { if (s[j + h] != s[i + h]) { break; } } lcp[rank[i] - 1] = h; } return lcp; } std::vector<std::vector<int> > create_sparse_table(int n, const std::vector<int> &lcp) { int h = 1; while ((1 << h) < n) { ++h; } std::vector<std::vector<int> > st(h + 1, std::vector<int>(n)); for (int i = 0; i < n; ++i) { st[0][i] = lcp[i]; } for (int j = 1; j <= h; ++j) { for (int i = 0; i <= n - (1 << j); ++i) { st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << (j-1))]); } } return st; } int top_bit(int t) { for (int i = 31; i >= 0; --i) { if ((1 << i) & t) { return i; } } assert (0); } int get_lcp(const std::vector<std::vector<int> > &st, int f, int s) { if (f > s) { std::swap(f, s); } assert (f < s); int diff = top_bit(s - f); return std::min(st[diff][f], st[diff][s - (1 << diff)]); } const int DEBUG = 0; int main(void){ int k; string s; cin >> k >> s; if (k == 0) { cout << s << endl; return 0; } int n = s.length(); VI sa = create_sa(s); VI sa_inv(n + 1); REP(i, 0, n + 1) { sa_inv[sa[i]] = i; } VI sat; int q = (n + k) / (k + 1); int r = q * (k + 1) - n; // 0 <= r <= k REP(i, 0, sa.size()) { int w = sa[i]; if (w <= n - q) { sat.push_back(w); } } int lo = -1; int hi = n - q + 1; while (hi - lo > 1) { int mid = (hi + lo) / 2; if (DEBUG) { cerr << "mid=" << s.substr(sat[mid]) << endl; } // try to divide, so that all the divided strings <= s[sat[mid]..] // We want to avoid making more than r strings of length q - 1. int rem = r; REP(i, 0, k + 1) { if (rem < 0) { break; } int idx = i * q - r + rem; if (DEBUG) { cerr << "s[idx..]=" << s.substr(idx) << endl; } if (idx >= n - q + 1) { break; } if (sa_inv[idx] > sa_inv[sat[mid]]) { rem--; } } if (rem >= 0) { hi = mid; } else { lo = mid; } } cout << s.substr(sat[hi], q) << endl; }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | kobae964 |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 4241 Byte |
Status | AC |
Exec Time | 90 ms |
Memory | 2032 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 | 3 ms | 256 KB |
subtask_01_02.txt | AC | 3 ms | 256 KB |
subtask_01_03.txt | AC | 3 ms | 256 KB |
subtask_01_04.txt | AC | 3 ms | 256 KB |
subtask_01_05.txt | AC | 3 ms | 256 KB |
subtask_01_06.txt | AC | 3 ms | 256 KB |
subtask_01_07.txt | AC | 3 ms | 256 KB |
subtask_01_08.txt | AC | 3 ms | 256 KB |
subtask_01_09.txt | AC | 3 ms | 256 KB |
subtask_01_10.txt | AC | 3 ms | 256 KB |
subtask_01_11.txt | AC | 3 ms | 256 KB |
subtask_01_12.txt | AC | 3 ms | 256 KB |
subtask_01_13.txt | AC | 3 ms | 256 KB |
subtask_01_14.txt | AC | 3 ms | 256 KB |
subtask_01_15.txt | AC | 3 ms | 256 KB |
subtask_01_16.txt | AC | 3 ms | 256 KB |
subtask_01_17.txt | AC | 3 ms | 256 KB |
subtask_02_01.txt | AC | 3 ms | 256 KB |
subtask_02_02.txt | AC | 3 ms | 256 KB |
subtask_02_03.txt | AC | 2 ms | 256 KB |
subtask_02_04.txt | AC | 3 ms | 256 KB |
subtask_02_05.txt | AC | 3 ms | 256 KB |
subtask_02_06.txt | AC | 3 ms | 256 KB |
subtask_02_07.txt | AC | 3 ms | 256 KB |
subtask_02_08.txt | AC | 3 ms | 256 KB |
subtask_02_09.txt | AC | 3 ms | 256 KB |
subtask_02_10.txt | AC | 3 ms | 256 KB |
subtask_02_11.txt | AC | 3 ms | 256 KB |
subtask_02_12.txt | AC | 3 ms | 256 KB |
subtask_02_13.txt | AC | 3 ms | 256 KB |
subtask_02_14.txt | AC | 3 ms | 256 KB |
subtask_02_ex1.txt | AC | 3 ms | 256 KB |
subtask_03_01.txt | AC | 3 ms | 256 KB |
subtask_03_02.txt | AC | 3 ms | 256 KB |
subtask_03_03.txt | AC | 3 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 | 3 ms | 256 KB |
subtask_03_07.txt | AC | 3 ms | 256 KB |
subtask_03_08.txt | AC | 3 ms | 256 KB |
subtask_03_09.txt | AC | 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 | AC | 3 ms | 256 KB |
subtask_03_14.txt | AC | 3 ms | 256 KB |
subtask_03_15.txt | AC | 3 ms | 256 KB |
subtask_03_ex2.txt | AC | 3 ms | 256 KB |
subtask_03_ex3.txt | AC | 3 ms | 256 KB |
subtask_04_01.txt | AC | 3 ms | 256 KB |
subtask_04_02.txt | AC | 3 ms | 256 KB |
subtask_04_03.txt | AC | 3 ms | 256 KB |
subtask_04_04.txt | AC | 3 ms | 256 KB |
subtask_04_05.txt | AC | 3 ms | 256 KB |
subtask_04_06.txt | AC | 3 ms | 256 KB |
subtask_04_07.txt | AC | 3 ms | 256 KB |
subtask_04_08.txt | AC | 3 ms | 256 KB |
subtask_04_09.txt | AC | 3 ms | 256 KB |
subtask_04_10.txt | AC | 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 | 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 | 89 ms | 2032 KB |
subtask_05_02.txt | AC | 90 ms | 2032 KB |
subtask_05_03.txt | AC | 86 ms | 2032 KB |
subtask_05_04.txt | AC | 86 ms | 2032 KB |
subtask_05_05.txt | AC | 86 ms | 2032 KB |
subtask_05_06.txt | AC | 87 ms | 2032 KB |
subtask_05_07.txt | AC | 87 ms | 2032 KB |
subtask_05_08.txt | AC | 86 ms | 1664 KB |
subtask_05_09.txt | AC | 6 ms | 512 KB |
subtask_05_10.txt | AC | 88 ms | 2032 KB |
subtask_05_11.txt | AC | 85 ms | 2032 KB |
subtask_05_12.txt | AC | 77 ms | 2032 KB |
subtask_05_13.txt | AC | 61 ms | 1840 KB |
subtask_05_14.txt | AC | 81 ms | 1960 KB |
subtask_05_15.txt | AC | 32 ms | 1080 KB |