Submission #1451890


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);
	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 2179 Byte
Status RE
Exec Time 113 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
AC × 3
AC × 13
WA × 4
AC × 26
WA × 6
AC × 42
WA × 7
AC × 55
WA × 8
RE × 1
AC × 68
WA × 9
RE × 2
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 2 ms 1024 KB
subtask_01_02.txt AC 1 ms 1024 KB
subtask_01_03.txt WA 1 ms 1024 KB
subtask_01_04.txt AC 1 ms 1024 KB
subtask_01_05.txt AC 1 ms 1024 KB
subtask_01_06.txt AC 1 ms 1024 KB
subtask_01_07.txt AC 2 ms 1024 KB
subtask_01_08.txt WA 1 ms 1024 KB
subtask_01_09.txt AC 1 ms 1024 KB
subtask_01_10.txt AC 1 ms 1024 KB
subtask_01_11.txt AC 1 ms 1024 KB
subtask_01_12.txt AC 1 ms 1024 KB
subtask_01_13.txt WA 1 ms 1024 KB
subtask_01_14.txt AC 1 ms 1024 KB
subtask_01_15.txt WA 1 ms 1024 KB
subtask_01_16.txt AC 1 ms 1024 KB
subtask_01_17.txt AC 1 ms 1024 KB
subtask_02_01.txt AC 1 ms 1024 KB
subtask_02_02.txt AC 1 ms 1024 KB
subtask_02_03.txt WA 1 ms 1024 KB
subtask_02_04.txt AC 1 ms 1024 KB
subtask_02_05.txt AC 1 ms 1024 KB
subtask_02_06.txt AC 2 ms 1024 KB
subtask_02_07.txt AC 2 ms 1024 KB
subtask_02_08.txt AC 2 ms 1024 KB
subtask_02_09.txt AC 1 ms 1024 KB
subtask_02_10.txt AC 2 ms 1024 KB
subtask_02_11.txt AC 1 ms 1024 KB
subtask_02_12.txt AC 1 ms 1024 KB
subtask_02_13.txt WA 1 ms 1024 KB
subtask_02_14.txt AC 1 ms 1024 KB
subtask_02_ex1.txt AC 1 ms 1024 KB
subtask_03_01.txt AC 1 ms 1024 KB
subtask_03_02.txt AC 2 ms 1024 KB
subtask_03_03.txt WA 1 ms 1024 KB
subtask_03_04.txt AC 2 ms 1024 KB
subtask_03_05.txt AC 2 ms 1024 KB
subtask_03_06.txt AC 2 ms 1024 KB
subtask_03_07.txt AC 2 ms 1024 KB
subtask_03_08.txt AC 1 ms 1024 KB
subtask_03_09.txt AC 2 ms 1024 KB
subtask_03_10.txt AC 2 ms 1024 KB
subtask_03_11.txt AC 2 ms 1024 KB
subtask_03_12.txt AC 2 ms 1024 KB
subtask_03_13.txt AC 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 AC 1 ms 1024 KB
subtask_03_ex3.txt AC 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 AC 2 ms 1152 KB
subtask_04_07.txt AC 2 ms 1152 KB
subtask_04_08.txt AC 3 ms 1152 KB
subtask_04_09.txt AC 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 RE 96 ms 1024 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 51 ms 3456 KB
subtask_05_02.txt AC 53 ms 3456 KB
subtask_05_03.txt WA 38 ms 3456 KB
subtask_05_04.txt AC 54 ms 3456 KB
subtask_05_05.txt AC 57 ms 3456 KB
subtask_05_06.txt AC 59 ms 3456 KB
subtask_05_07.txt AC 59 ms 3456 KB
subtask_05_08.txt AC 104 ms 4424 KB
subtask_05_09.txt AC 48 ms 5328 KB
subtask_05_10.txt AC 59 ms 3456 KB
subtask_05_11.txt AC 64 ms 3456 KB
subtask_05_12.txt RE 113 ms 2304 KB
subtask_05_13.txt AC 59 ms 2816 KB
subtask_05_14.txt AC 69 ms 3328 KB
subtask_05_15.txt AC 25 ms 2048 KB