CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel)

Submission #1451902

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
const int MAXN = 200005;

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

Task問題 B - 数字列をカンマで分ける問題 / Problem where Commas Separate Digits
User nameユーザ名 koosaga
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 RE
Score得点 400
Source lengthソースコード長 2229 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./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);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask_02_ex1.txt,subtask_03_ex2.txt,subtask_03_ex3.txt
Dataset1 100 / 100 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 100 / 100 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 200 / 200 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 0 / 200 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 0 / 400 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 2 ms 4608 KB
subtask_01_02.txt AC 2 ms 4608 KB
subtask_01_03.txt AC 2 ms 4608 KB
subtask_01_04.txt AC 2 ms 4608 KB
subtask_01_05.txt AC 2 ms 4608 KB
subtask_01_06.txt AC 2 ms 4608 KB
subtask_01_07.txt AC 2 ms 4608 KB
subtask_01_08.txt AC 2 ms 4608 KB
subtask_01_09.txt AC 2 ms 4608 KB
subtask_01_10.txt AC 2 ms 4608 KB
subtask_01_11.txt AC 2 ms 4608 KB
subtask_01_12.txt AC 2 ms 4608 KB
subtask_01_13.txt AC 2 ms 4608 KB
subtask_01_14.txt AC 2 ms 4608 KB
subtask_01_15.txt AC 2 ms 4608 KB
subtask_01_16.txt AC 2 ms 4608 KB
subtask_01_17.txt AC 2 ms 4608 KB
subtask_02_01.txt AC 2 ms 4608 KB
subtask_02_02.txt AC 2 ms 4608 KB
subtask_02_03.txt AC 2 ms 4608 KB
subtask_02_04.txt AC 2 ms 4608 KB
subtask_02_05.txt AC 2 ms 4608 KB
subtask_02_06.txt AC 2 ms 4608 KB
subtask_02_07.txt AC 2 ms 4608 KB
subtask_02_08.txt AC 2 ms 4608 KB
subtask_02_09.txt AC 2 ms 4608 KB
subtask_02_10.txt AC 2 ms 4608 KB
subtask_02_11.txt AC 2 ms 4608 KB
subtask_02_12.txt AC 2 ms 4608 KB
subtask_02_13.txt AC 2 ms 4608 KB
subtask_02_14.txt AC 2 ms 4608 KB
subtask_02_ex1.txt AC 2 ms 4608 KB
subtask_03_01.txt AC 2 ms 4608 KB
subtask_03_02.txt AC 2 ms 4608 KB
subtask_03_03.txt AC 2 ms 4608 KB
subtask_03_04.txt AC 2 ms 4608 KB
subtask_03_05.txt AC 2 ms 4608 KB
subtask_03_06.txt AC 2 ms 4608 KB
subtask_03_07.txt AC 2 ms 4608 KB
subtask_03_08.txt AC 2 ms 4608 KB
subtask_03_09.txt AC 2 ms 4608 KB
subtask_03_10.txt AC 2 ms 4608 KB
subtask_03_11.txt AC 2 ms 4608 KB
subtask_03_12.txt AC 2 ms 4608 KB
subtask_03_13.txt AC 2 ms 4608 KB
subtask_03_14.txt AC 2 ms 4608 KB
subtask_03_15.txt AC 2 ms 4608 KB
subtask_03_ex2.txt AC 2 ms 4608 KB
subtask_03_ex3.txt AC 2 ms 4608 KB
subtask_04_01.txt AC 3 ms 4736 KB
subtask_04_02.txt AC 3 ms 4736 KB
subtask_04_03.txt AC 3 ms 4736 KB
subtask_04_04.txt AC 3 ms 4736 KB
subtask_04_05.txt AC 3 ms 4736 KB
subtask_04_06.txt AC 3 ms 4736 KB
subtask_04_07.txt AC 3 ms 4736 KB
subtask_04_08.txt AC 4 ms 4736 KB
subtask_04_09.txt AC 4 ms 4736 KB
subtask_04_10.txt AC 3 ms 4736 KB
subtask_04_11.txt AC 4 ms 4736 KB
subtask_04_12.txt RE
subtask_04_13.txt AC 3 ms 4608 KB
subtask_04_14.txt AC 2 ms 4608 KB
subtask_04_15.txt AC 3 ms 4736 KB
subtask_05_01.txt AC 51 ms 5888 KB
subtask_05_02.txt AC 54 ms 5888 KB
subtask_05_03.txt AC 51 ms 5888 KB
subtask_05_04.txt AC 54 ms 5888 KB
subtask_05_05.txt AC 57 ms 5888 KB
subtask_05_06.txt AC 59 ms 5888 KB
subtask_05_07.txt AC 59 ms 5888 KB
subtask_05_08.txt AC 163 ms 6392 KB
subtask_05_09.txt AC 157 ms 6904 KB
subtask_05_10.txt AC 59 ms 5888 KB
subtask_05_11.txt AC 66 ms 5888 KB
subtask_05_12.txt RE
subtask_05_13.txt AC 60 ms 5504 KB
subtask_05_14.txt AC 71 ms 5760 KB
subtask_05_15.txt AC 26 ms 5120 KB