Submission #1451723

---

Source Code Expand

#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 Info

Compile Error

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

Judge Result