CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel)

Submission #1451723

Source codeソースコード

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 100000;

int D[MAXN + 1];
void radixSort(const int *A, const int *B, int *C, int N, int M) {
	int i;
	for (i = 0; i <= M; i++) D[i] = 0;
	for (i = 0; i < N; i++) D[B[A[i]]]++;
	for (i = 1; i <= M; i++) D[i] += D[i - 1];
	for (i = N; i--; C[--D[B[A[i]]]] = A[i]);
}

int B[MAXN + 1];
int T[MAXN];
void suffixArray(const char *A, int *C, int N) {
	int i, j, k, l;
	for (i = 0; i < N; i++) {
		B[i] = A[i];
		T[i] = i;
	}
	radixSort(T, B, C, N, 128);
	for (i = k = 1; i < N && k < N; i <<= 1) {
		for (k = 0; k < i; k++) T[k] = k - i + N;
		for (j = 0; j < N; j++) if (C[j] >= i) T[k++] = C[j] - i;
		radixSort(T, B, C, N, N);
		T[C[0]] = k = 1;
		for (j = 1; j < N; j++) {
			if (B[C[j]] != B[C[j - 1]] || B[C[j] + i] != B[C[j - 1] + i]) k++;
			T[C[j]] = k;
		}
		for (j = 0; j < N; j++) B[j] = T[j];
	}
}

char S[100001];
int R[100001];

int main() {
	int LL, RR, MM;
	int i, j, n, m;
	scanf("%d%s", &m, S);
	n = strlen(S);
	suffixArray(S, R, n);
	for (i = 0; i < n; i++) T[R[i]] = i;
	if (n % (m + 1) == 0) {
		j = 0;
		for (i = 1; i <= m; i++) if (T[i * (n / (m + 1))] > T[j]) j = i * (n / (m + 1));
		S[j + (n / (m + 1))] = 0;
		puts(S + j);
		return 0;
	}
	LL = 0;
	RR = n - 1;
	while (LL < RR) {
		MM = LL + RR >> 1;
		D[0] = 0;
		for (i = 1; i <= n; i++) D[i] = 1e9;
		for (i = 0; i < n; i++) {
			if (i + n / (m + 1) <= n) D[i + n / (m + 1)] = min(D[i + n / (m + 1)], D[i] + 1);
			if (i + n / (m + 1) + 1 <= n && T[i] <= MM) D[i + n / (m + 1) + 1] = min(D[i + n / (m + 1) + 1], D[i] + 1);
		}
		if (D[n] <= m + 1) RR = MM;
		else LL = MM + 1;
	}
	S[R[LL] + n / (m + 1) + 1] = 0;
	puts(S + R[LL]);
}

Submission

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

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:46:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%s", &m, S);
^

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 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,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 400 / 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 1 ms 128 KB
subtask_01_02.txt AC 1 ms 128 KB
subtask_01_03.txt AC 1 ms 128 KB
subtask_01_04.txt AC 1 ms 128 KB
subtask_01_05.txt AC 1 ms 128 KB
subtask_01_06.txt AC 1 ms 128 KB
subtask_01_07.txt AC 1 ms 128 KB
subtask_01_08.txt AC 1 ms 128 KB
subtask_01_09.txt AC 1 ms 128 KB
subtask_01_10.txt AC 1 ms 128 KB
subtask_01_11.txt AC 1 ms 128 KB
subtask_01_12.txt AC 1 ms 128 KB
subtask_01_13.txt AC 1 ms 128 KB
subtask_01_14.txt AC 1 ms 128 KB
subtask_01_15.txt AC 1 ms 128 KB
subtask_01_16.txt AC 1 ms 128 KB
subtask_01_17.txt AC 1 ms 128 KB
subtask_02_01.txt AC 1 ms 128 KB
subtask_02_02.txt AC 1 ms 128 KB
subtask_02_03.txt AC 1 ms 128 KB
subtask_02_04.txt AC 1 ms 128 KB
subtask_02_05.txt AC 1 ms 128 KB
subtask_02_06.txt AC 1 ms 128 KB
subtask_02_07.txt AC 1 ms 128 KB
subtask_02_08.txt AC 1 ms 128 KB
subtask_02_09.txt AC 1 ms 128 KB
subtask_02_10.txt AC 1 ms 128 KB
subtask_02_11.txt AC 1 ms 128 KB
subtask_02_12.txt AC 1 ms 128 KB
subtask_02_13.txt AC 1 ms 128 KB
subtask_02_14.txt AC 1 ms 128 KB
subtask_02_ex1.txt AC 1 ms 128 KB
subtask_03_01.txt AC 1 ms 128 KB
subtask_03_02.txt AC 1 ms 128 KB
subtask_03_03.txt AC 1 ms 128 KB
subtask_03_04.txt AC 1 ms 128 KB
subtask_03_05.txt AC 1 ms 128 KB
subtask_03_06.txt AC 1 ms 128 KB
subtask_03_07.txt AC 1 ms 128 KB
subtask_03_08.txt AC 1 ms 128 KB
subtask_03_09.txt AC 1 ms 128 KB
subtask_03_10.txt AC 1 ms 128 KB
subtask_03_11.txt AC 1 ms 128 KB
subtask_03_12.txt AC 1 ms 128 KB
subtask_03_13.txt AC 1 ms 128 KB
subtask_03_14.txt AC 1 ms 128 KB
subtask_03_15.txt AC 1 ms 128 KB
subtask_03_ex2.txt AC 1 ms 128 KB
subtask_03_ex3.txt AC 1 ms 128 KB
subtask_04_01.txt AC 1 ms 256 KB
subtask_04_02.txt AC 1 ms 256 KB
subtask_04_03.txt AC 1 ms 256 KB
subtask_04_04.txt AC 1 ms 256 KB
subtask_04_05.txt AC 1 ms 256 KB
subtask_04_06.txt AC 1 ms 256 KB
subtask_04_07.txt AC 1 ms 256 KB
subtask_04_08.txt AC 1 ms 256 KB
subtask_04_09.txt AC 1 ms 256 KB
subtask_04_10.txt AC 1 ms 256 KB
subtask_04_11.txt AC 1 ms 256 KB
subtask_04_12.txt AC 1 ms 256 KB
subtask_04_13.txt AC 1 ms 128 KB
subtask_04_14.txt AC 1 ms 128 KB
subtask_04_15.txt AC 1 ms 128 KB
subtask_05_01.txt AC 15 ms 1792 KB
subtask_05_02.txt AC 17 ms 1792 KB
subtask_05_03.txt AC 10 ms 1792 KB
subtask_05_04.txt AC 10 ms 1792 KB
subtask_05_05.txt AC 15 ms 1792 KB
subtask_05_06.txt AC 9 ms 1792 KB
subtask_05_07.txt AC 9 ms 1792 KB
subtask_05_08.txt AC 9 ms 1920 KB
subtask_05_09.txt AC 10 ms 1920 KB
subtask_05_10.txt AC 16 ms 1792 KB
subtask_05_11.txt AC 22 ms 1792 KB
subtask_05_12.txt AC 22 ms 1792 KB
subtask_05_13.txt AC 12 ms 1408 KB
subtask_05_14.txt AC 14 ms 1664 KB
subtask_05_15.txt AC 7 ms 896 KB