Submission #1451935


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;
			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];
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 400
Code Size 2229 Byte
Status RE
Exec Time 164 ms
Memory 12920 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:87: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 100 / 100 100 / 100 200 / 200 0 / 200 0 / 400
Status
AC × 3
AC × 17
AC × 32
AC × 49
AC × 63
RE × 1
AC × 77
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 4 ms 11136 KB
subtask_01_02.txt AC 4 ms 11136 KB
subtask_01_03.txt AC 4 ms 11136 KB
subtask_01_04.txt AC 4 ms 11136 KB
subtask_01_05.txt AC 4 ms 11136 KB
subtask_01_06.txt AC 4 ms 11136 KB
subtask_01_07.txt AC 4 ms 11136 KB
subtask_01_08.txt AC 4 ms 11136 KB
subtask_01_09.txt AC 4 ms 11136 KB
subtask_01_10.txt AC 4 ms 11136 KB
subtask_01_11.txt AC 4 ms 11136 KB
subtask_01_12.txt AC 4 ms 11136 KB
subtask_01_13.txt AC 4 ms 11136 KB
subtask_01_14.txt AC 4 ms 11136 KB
subtask_01_15.txt AC 4 ms 11136 KB
subtask_01_16.txt AC 4 ms 11136 KB
subtask_01_17.txt AC 4 ms 11136 KB
subtask_02_01.txt AC 4 ms 11136 KB
subtask_02_02.txt AC 4 ms 11136 KB
subtask_02_03.txt AC 4 ms 11136 KB
subtask_02_04.txt AC 4 ms 11136 KB
subtask_02_05.txt AC 4 ms 11136 KB
subtask_02_06.txt AC 4 ms 11136 KB
subtask_02_07.txt AC 4 ms 11136 KB
subtask_02_08.txt AC 4 ms 11136 KB
subtask_02_09.txt AC 4 ms 11136 KB
subtask_02_10.txt AC 4 ms 11136 KB
subtask_02_11.txt AC 4 ms 11136 KB
subtask_02_12.txt AC 4 ms 11136 KB
subtask_02_13.txt AC 4 ms 11136 KB
subtask_02_14.txt AC 4 ms 11136 KB
subtask_02_ex1.txt AC 4 ms 11136 KB
subtask_03_01.txt AC 4 ms 11136 KB
subtask_03_02.txt AC 4 ms 11136 KB
subtask_03_03.txt AC 4 ms 11136 KB
subtask_03_04.txt AC 4 ms 11136 KB
subtask_03_05.txt AC 4 ms 11136 KB
subtask_03_06.txt AC 4 ms 11136 KB
subtask_03_07.txt AC 4 ms 11136 KB
subtask_03_08.txt AC 4 ms 11136 KB
subtask_03_09.txt AC 4 ms 11136 KB
subtask_03_10.txt AC 4 ms 11136 KB
subtask_03_11.txt AC 4 ms 11136 KB
subtask_03_12.txt AC 4 ms 11136 KB
subtask_03_13.txt AC 4 ms 11136 KB
subtask_03_14.txt AC 4 ms 11136 KB
subtask_03_15.txt AC 4 ms 11136 KB
subtask_03_ex2.txt AC 4 ms 11136 KB
subtask_03_ex3.txt AC 4 ms 11136 KB
subtask_04_01.txt AC 5 ms 11136 KB
subtask_04_02.txt AC 5 ms 11136 KB
subtask_04_03.txt AC 5 ms 11136 KB
subtask_04_04.txt AC 5 ms 11136 KB
subtask_04_05.txt AC 5 ms 11136 KB
subtask_04_06.txt AC 5 ms 11136 KB
subtask_04_07.txt AC 5 ms 11136 KB
subtask_04_08.txt AC 6 ms 11136 KB
subtask_04_09.txt AC 6 ms 11136 KB
subtask_04_10.txt AC 5 ms 11136 KB
subtask_04_11.txt AC 6 ms 11136 KB
subtask_04_12.txt RE 101 ms 9088 KB
subtask_04_13.txt AC 4 ms 11136 KB
subtask_04_14.txt AC 4 ms 11136 KB
subtask_04_15.txt AC 4 ms 11136 KB
subtask_05_01.txt AC 53 ms 11904 KB
subtask_05_02.txt AC 56 ms 11904 KB
subtask_05_03.txt AC 53 ms 11904 KB
subtask_05_04.txt AC 56 ms 11904 KB
subtask_05_05.txt AC 59 ms 11904 KB
subtask_05_06.txt AC 61 ms 11904 KB
subtask_05_07.txt AC 61 ms 11904 KB
subtask_05_08.txt AC 164 ms 12408 KB
subtask_05_09.txt AC 158 ms 12920 KB
subtask_05_10.txt AC 61 ms 11904 KB
subtask_05_11.txt AC 68 ms 11904 KB
subtask_05_12.txt RE 130 ms 9088 KB
subtask_05_13.txt AC 61 ms 11648 KB
subtask_05_14.txt AC 73 ms 11776 KB
subtask_05_15.txt AC 28 ms 11392 KB