Submission #1451938
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long lint; typedef pair<int, int> pi; const int mod = 1e9 + 7; const int MAXN = 400005; namespace sfxarray{ int ord[MAXN], nord[MAXN], cnt[MAXN], aux[MAXN]; void solve(int n, char *str, int *sfx, int *rev, int *lcp){ int p = 1; memset(ord, 0, sizeof(ord)); for(int i=0; i<n; i++){ sfx[i] = i; rev[i] = i; ord[i] = str[i]; } return; ord[n] = 255; int pnt = 1; while(1){ memset(cnt, 0, sizeof(cnt)); for(int i=0; i<n; i++){ cnt[ord[min(i+p, n)]]++; } for(int i=1; i<=n || i<=255; i++){ cnt[i] += cnt[i-1]; } for(int i=n-1; i>=0; i--){ aux[--cnt[ord[min(i+p, n)]]] = i; } memset(cnt, 0, sizeof(cnt)); for(int i=0; i<n; i++){ cnt[ord[i]]++; } for(int i=1; i<=n || i<=255; i++){ cnt[i] += cnt[i-1]; } for(int i=n-1; i>=0; i--){ sfx[--cnt[ord[aux[i]]]] = aux[i]; } if(pnt == n) break; pnt = 1; nord[sfx[0]] = 1; for(int i=1; i<n; i++){ if(ord[sfx[i-1]] != ord[sfx[i]] || ord[sfx[i-1] + p] != ord[sfx[i] + p]){ pnt++; } nord[sfx[i]] = pnt; } memcpy(ord, nord, sizeof(int) * n); p *= 2; } for(int i=0; i<n; i++){ rev[sfx[i]] = i; } int h = 0; for(int i=0; i<n; i++){ if(rev[i]){ int prv = sfx[rev[i] - 1]; while(str[prv + h] == str[i + h]) h++; lcp[rev[i]] = h; } h = max(h-1, 0); } } } int n, k; char str[MAXN]; int sfx[MAXN], rev[MAXN], lcp[MAXN]; int dp[MAXN]; priority_queue<pi, vector<pi>, greater<pi> > pq; int trial(int v){ while(!pq.empty()) pq.pop(); int l = (n + k - 1) / k; pq.push(pi(0, 0)); for(int i=1; i<=n; i++){ while(!pq.empty() && pq.top().second < i - l) pq.pop(); if(!pq.empty() && pq.top().second == i - l && rev[i - l] > v) pq.pop(); dp[i] = (pq.empty() ? 1e9 : pq.top().first) + 1; pq.push(pi(dp[i], i)); } return dp[n]; } int main(){ scanf("%d %s",&k,str); k++; n = strlen(str); sfxarray::solve(n, str, sfx, rev, lcp); int s = 0, e = n-1; while(s != e){ int m = (s+e)/2; if(trial(m) <= k) e = m; else s = m+1; } for(int j=sfx[s]; j<sfx[s] + (n+k-1)/k; j++) printf("%c", str[j]); }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | koosaga |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2251 Byte |
Status | WA |
Exec Time | 142 ms |
Memory | 10488 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:89:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d %s",&k,str); ^
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 | AC | 3 ms | 9088 KB |
subtask_01_02.txt | AC | 3 ms | 9088 KB |
subtask_01_03.txt | WA | 3 ms | 9088 KB |
subtask_01_04.txt | AC | 3 ms | 9088 KB |
subtask_01_05.txt | AC | 3 ms | 9088 KB |
subtask_01_06.txt | AC | 3 ms | 9088 KB |
subtask_01_07.txt | AC | 3 ms | 9088 KB |
subtask_01_08.txt | AC | 3 ms | 9088 KB |
subtask_01_09.txt | AC | 3 ms | 9088 KB |
subtask_01_10.txt | AC | 3 ms | 9088 KB |
subtask_01_11.txt | AC | 3 ms | 9088 KB |
subtask_01_12.txt | AC | 3 ms | 9088 KB |
subtask_01_13.txt | AC | 3 ms | 9088 KB |
subtask_01_14.txt | AC | 3 ms | 9088 KB |
subtask_01_15.txt | WA | 3 ms | 9088 KB |
subtask_01_16.txt | AC | 3 ms | 9088 KB |
subtask_01_17.txt | AC | 3 ms | 9088 KB |
subtask_02_01.txt | WA | 3 ms | 9088 KB |
subtask_02_02.txt | WA | 3 ms | 9088 KB |
subtask_02_03.txt | WA | 3 ms | 9088 KB |
subtask_02_04.txt | WA | 3 ms | 9088 KB |
subtask_02_05.txt | WA | 3 ms | 9088 KB |
subtask_02_06.txt | AC | 3 ms | 9088 KB |
subtask_02_07.txt | WA | 3 ms | 9088 KB |
subtask_02_08.txt | AC | 3 ms | 9088 KB |
subtask_02_09.txt | AC | 3 ms | 9088 KB |
subtask_02_10.txt | AC | 3 ms | 9088 KB |
subtask_02_11.txt | AC | 3 ms | 9088 KB |
subtask_02_12.txt | WA | 3 ms | 9088 KB |
subtask_02_13.txt | WA | 3 ms | 9088 KB |
subtask_02_14.txt | WA | 3 ms | 9088 KB |
subtask_02_ex1.txt | WA | 3 ms | 9088 KB |
subtask_03_01.txt | WA | 3 ms | 9088 KB |
subtask_03_02.txt | WA | 3 ms | 9088 KB |
subtask_03_03.txt | WA | 3 ms | 9088 KB |
subtask_03_04.txt | WA | 3 ms | 9088 KB |
subtask_03_05.txt | WA | 3 ms | 9088 KB |
subtask_03_06.txt | WA | 3 ms | 9088 KB |
subtask_03_07.txt | WA | 3 ms | 9088 KB |
subtask_03_08.txt | WA | 3 ms | 9088 KB |
subtask_03_09.txt | AC | 3 ms | 9088 KB |
subtask_03_10.txt | WA | 3 ms | 9088 KB |
subtask_03_11.txt | AC | 3 ms | 9088 KB |
subtask_03_12.txt | WA | 3 ms | 9088 KB |
subtask_03_13.txt | WA | 3 ms | 9088 KB |
subtask_03_14.txt | WA | 3 ms | 9088 KB |
subtask_03_15.txt | WA | 3 ms | 9088 KB |
subtask_03_ex2.txt | AC | 3 ms | 9088 KB |
subtask_03_ex3.txt | WA | 3 ms | 9088 KB |
subtask_04_01.txt | WA | 3 ms | 9088 KB |
subtask_04_02.txt | WA | 4 ms | 9088 KB |
subtask_04_03.txt | WA | 3 ms | 9088 KB |
subtask_04_04.txt | WA | 3 ms | 9088 KB |
subtask_04_05.txt | WA | 4 ms | 9088 KB |
subtask_04_06.txt | WA | 4 ms | 9088 KB |
subtask_04_07.txt | WA | 4 ms | 9088 KB |
subtask_04_08.txt | WA | 4 ms | 9088 KB |
subtask_04_09.txt | AC | 5 ms | 9088 KB |
subtask_04_10.txt | AC | 4 ms | 9088 KB |
subtask_04_11.txt | AC | 4 ms | 9088 KB |
subtask_04_12.txt | WA | 4 ms | 9088 KB |
subtask_04_13.txt | WA | 3 ms | 9088 KB |
subtask_04_14.txt | WA | 3 ms | 9088 KB |
subtask_04_15.txt | WA | 3 ms | 9088 KB |
subtask_05_01.txt | WA | 36 ms | 9472 KB |
subtask_05_02.txt | WA | 39 ms | 9472 KB |
subtask_05_03.txt | WA | 36 ms | 9472 KB |
subtask_05_04.txt | WA | 41 ms | 9472 KB |
subtask_05_05.txt | WA | 40 ms | 9472 KB |
subtask_05_06.txt | WA | 42 ms | 9472 KB |
subtask_05_07.txt | WA | 45 ms | 9472 KB |
subtask_05_08.txt | WA | 141 ms | 9976 KB |
subtask_05_09.txt | AC | 142 ms | 10488 KB |
subtask_05_10.txt | WA | 42 ms | 9472 KB |
subtask_05_11.txt | AC | 42 ms | 9472 KB |
subtask_05_12.txt | WA | 42 ms | 9472 KB |
subtask_05_13.txt | WA | 36 ms | 9344 KB |
subtask_05_14.txt | WA | 53 ms | 9472 KB |
subtask_05_15.txt | WA | 19 ms | 9216 KB |