Submission #1451942
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 = 100005; 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; ord[i] = str[i]; } 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]; int trial(int v){ int l = (n + k - 1) / k; priority_queue<pi, vector<pi>, greater<pi> > pq; 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.top().first + 1; pq.push(pi(dp[i], i)); } return dp[n]; } int main(){ scanf("%d %s",&k,str); str[n] = '9' + 1; k++; n = strlen(str); sfxarray::solve(n + 1, 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 | 2203 Byte |
Status | WA |
Exec Time | 94 ms |
Memory | 5328 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:86: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 | WA | 2 ms | 1024 KB |
subtask_01_02.txt | WA | 2 ms | 1024 KB |
subtask_01_03.txt | WA | 2 ms | 1024 KB |
subtask_01_04.txt | WA | 2 ms | 1024 KB |
subtask_01_05.txt | WA | 2 ms | 1024 KB |
subtask_01_06.txt | WA | 2 ms | 1024 KB |
subtask_01_07.txt | WA | 2 ms | 1024 KB |
subtask_01_08.txt | WA | 2 ms | 1024 KB |
subtask_01_09.txt | WA | 2 ms | 1024 KB |
subtask_01_10.txt | WA | 2 ms | 1024 KB |
subtask_01_11.txt | WA | 2 ms | 1024 KB |
subtask_01_12.txt | WA | 2 ms | 1024 KB |
subtask_01_13.txt | WA | 2 ms | 1024 KB |
subtask_01_14.txt | WA | 2 ms | 1024 KB |
subtask_01_15.txt | WA | 2 ms | 1024 KB |
subtask_01_16.txt | WA | 2 ms | 1024 KB |
subtask_01_17.txt | WA | 2 ms | 1024 KB |
subtask_02_01.txt | WA | 2 ms | 1024 KB |
subtask_02_02.txt | AC | 2 ms | 1024 KB |
subtask_02_03.txt | WA | 2 ms | 1024 KB |
subtask_02_04.txt | AC | 2 ms | 1024 KB |
subtask_02_05.txt | AC | 2 ms | 1024 KB |
subtask_02_06.txt | AC | 2 ms | 1024 KB |
subtask_02_07.txt | WA | 2 ms | 1024 KB |
subtask_02_08.txt | WA | 2 ms | 1024 KB |
subtask_02_09.txt | WA | 2 ms | 1024 KB |
subtask_02_10.txt | AC | 2 ms | 1024 KB |
subtask_02_11.txt | WA | 2 ms | 1024 KB |
subtask_02_12.txt | AC | 2 ms | 1024 KB |
subtask_02_13.txt | WA | 2 ms | 1024 KB |
subtask_02_14.txt | AC | 2 ms | 1024 KB |
subtask_02_ex1.txt | AC | 2 ms | 1024 KB |
subtask_03_01.txt | AC | 2 ms | 1024 KB |
subtask_03_02.txt | AC | 2 ms | 1024 KB |
subtask_03_03.txt | WA | 2 ms | 1024 KB |
subtask_03_04.txt | AC | 2 ms | 1024 KB |
subtask_03_05.txt | WA | 2 ms | 1024 KB |
subtask_03_06.txt | AC | 2 ms | 1024 KB |
subtask_03_07.txt | WA | 2 ms | 1024 KB |
subtask_03_08.txt | WA | 2 ms | 1024 KB |
subtask_03_09.txt | WA | 2 ms | 1024 KB |
subtask_03_10.txt | AC | 2 ms | 1024 KB |
subtask_03_11.txt | WA | 2 ms | 1024 KB |
subtask_03_12.txt | AC | 2 ms | 1024 KB |
subtask_03_13.txt | WA | 2 ms | 1024 KB |
subtask_03_14.txt | AC | 2 ms | 1024 KB |
subtask_03_15.txt | AC | 2 ms | 1024 KB |
subtask_03_ex2.txt | WA | 2 ms | 1024 KB |
subtask_03_ex3.txt | WA | 2 ms | 1024 KB |
subtask_04_01.txt | AC | 2 ms | 1152 KB |
subtask_04_02.txt | AC | 2 ms | 1152 KB |
subtask_04_03.txt | WA | 2 ms | 1152 KB |
subtask_04_04.txt | AC | 2 ms | 1152 KB |
subtask_04_05.txt | AC | 2 ms | 1152 KB |
subtask_04_06.txt | WA | 2 ms | 1152 KB |
subtask_04_07.txt | WA | 2 ms | 1152 KB |
subtask_04_08.txt | WA | 3 ms | 1152 KB |
subtask_04_09.txt | WA | 2 ms | 1152 KB |
subtask_04_10.txt | AC | 2 ms | 1152 KB |
subtask_04_11.txt | AC | 3 ms | 1152 KB |
subtask_04_12.txt | AC | 3 ms | 1152 KB |
subtask_04_13.txt | AC | 2 ms | 1024 KB |
subtask_04_14.txt | AC | 2 ms | 1024 KB |
subtask_04_15.txt | AC | 2 ms | 1024 KB |
subtask_05_01.txt | AC | 53 ms | 3456 KB |
subtask_05_02.txt | AC | 52 ms | 3456 KB |
subtask_05_03.txt | WA | 39 ms | 3456 KB |
subtask_05_04.txt | AC | 54 ms | 3456 KB |
subtask_05_05.txt | AC | 58 ms | 3456 KB |
subtask_05_06.txt | AC | 57 ms | 3456 KB |
subtask_05_07.txt | AC | 58 ms | 3456 KB |
subtask_05_08.txt | WA | 94 ms | 4428 KB |
subtask_05_09.txt | WA | 47 ms | 5328 KB |
subtask_05_10.txt | AC | 60 ms | 3456 KB |
subtask_05_11.txt | AC | 68 ms | 3456 KB |
subtask_05_12.txt | AC | 68 ms | 3456 KB |
subtask_05_13.txt | AC | 60 ms | 2944 KB |
subtask_05_14.txt | AC | 70 ms | 3328 KB |
subtask_05_15.txt | AC | 26 ms | 2048 KB |