Submission #1022041
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> P; typedef pair<ll, ll> Pll; typedef vector<int> Vi; //typedef tuple<int, int, int> T; #define FOR(i,s,x) for(int i=s;i<(int)(x);i++) #define REP(i,x) FOR(i,0,x) #define ALL(c) c.begin(), c.end() #define DUMP( x ) cerr << #x << " = " << ( x ) << endl const int dr[4] = {-1, 0, 1, 0}; const int dc[4] = {0, 1, 0, -1}; struct SuffixArray { int N, k; string S; vector<int> sa, rank, tmp; vector<int> lpc, rank_lpc; SuffixArray(string S) : S(S) { N = S.size(); sa.resize(N+1), rank.resize(N+1), tmp.resize(N+1); construct_sa(); } bool compare_sa(int i, int j) { if (rank[i] != rank[j]) { return rank[i] < rank[j]; } else { int ri = i + k <= N ? rank[i + k] : -1; int rj = j + k <= N ? rank[j + k] : -1; return ri < rj; } } void construct_sa() { for (int i = 0; i <= N; i++) { sa[i] = i; rank[i] = i < N ? S[i] : -1; } for (k = 1; k <= N; k *= 2) { sort(sa.begin(), sa.end(), [&] (const int & i, const int & j) { return compare_sa(i, j); }); tmp[sa[0]] = 0; for (int i = 1; i <= N; i++) { tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0); } for (int i = 0; i <= N; i++) rank[i] = tmp[i]; } } bool contain(string T) { int left = 0, right = N; while (left - right > 1) { int mid = (left + right) / 2; (S.compare(sa[mid], T.length(), T) < 0 ? left : right) = mid; } return S.compare(sa[right], T.length(), T) == 0; } void construct_lpc() { lpc.resize(N), rank_lpc.resize(N+1); for (int i = 0; i <= N; i++) rank_lpc[sa[i]] = i; int h = 0; lpc[0] = 0; for (int i = 0; i < N; i++) { int j = sa[rank[i] - 1]; if (h > 0) h--; for (; j + h < N and i + h < N; h++) { if (S[j + h] != S[i + h]) break; } lpc[rank[i] - 1] = h; } } }; int main() { // use scanf in CodeForces! cin.tie(0); ios_base::sync_with_stdio(false); int K; cin >> K; string S; cin >> S; int N = S.size(); SuffixArray sa(S); vector<int> cand; int L = ((int)S.size() + K) / (K + 1); REP(i, sa.sa.size()) { if (sa.sa[i] + L <= N) cand.push_back(sa.sa[i]); } function<bool (int)> check = [&](int mid) { int cnt = 0, cur = 0, prev = 0; while (cur < N) { if (sa.rank[cur] <= sa.rank[cand[mid]]) { cur += L; } else { cur += L - 1; } cnt++; if (cnt - 1 > K) return false; } return cnt - 1 <= K; }; int left = -1, right = cand.size() - 1; while (left + 1 < right) { int mid = (left + right) / 2; (check(mid) ? right : left) = mid; } cout << S.substr(cand[right], L) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | n_knuu |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2925 Byte |
Status | AC |
Exec Time | 88 ms |
Memory | 2252 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 | 384 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 | 3 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 | 384 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 | 384 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 | 384 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 | 86 ms | 2252 KB |
subtask_05_02.txt | AC | 88 ms | 2252 KB |
subtask_05_03.txt | AC | 85 ms | 2252 KB |
subtask_05_04.txt | AC | 84 ms | 2252 KB |
subtask_05_05.txt | AC | 83 ms | 2252 KB |
subtask_05_06.txt | AC | 83 ms | 2252 KB |
subtask_05_07.txt | AC | 82 ms | 2252 KB |
subtask_05_08.txt | AC | 82 ms | 2000 KB |
subtask_05_09.txt | AC | 81 ms | 1872 KB |
subtask_05_10.txt | AC | 85 ms | 2252 KB |
subtask_05_11.txt | AC | 81 ms | 2252 KB |
subtask_05_12.txt | AC | 73 ms | 2252 KB |
subtask_05_13.txt | AC | 59 ms | 1916 KB |
subtask_05_14.txt | AC | 76 ms | 2240 KB |
subtask_05_15.txt | AC | 31 ms | 1280 KB |