Submission #1007126

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
const int MX = 220000;
int n;
char s[MX];
int cc[MX];
int p[MX];
int p2[MX];
int c[MX];
int c2[MX];
int en[MX];
int ans[MX];
int nm(int a, int b) {
	if (a < 0)
		return a + b;
	if (a >= b)
		return a - b;
	return a;
}

void sa() {
	n += 1;
	for (int i = 0; i < n; ++i)
		c[i] = s[i];
	for (int i = 0; i < n; ++i)
		++cc[c[i] + 1];
	for (int i = 1; i < MX; ++i)
		cc[i] += cc[i - 1];
	for (int i = 0; i < n; ++i)
		p[cc[c[i]]++] = i;
	for (int k = 0; (1 << k) < n; ++k) {
		for (int i = 0; i < n; ++i)
			p[i] = nm(p[i] - (1 << k), n);
		memset(cc, 0, sizeof(cc));
		for (int i = 0; i < n; ++i)
			++cc[c[i] + 1];
		for (int i = 1; i < MX; ++i)
			cc[i] += cc[i - 1];
		for (int i = 0; i < n; ++i)
			p2[cc[c[p[i]]]++] = p[i];
		memcpy(p, p2, sizeof(p));
		int now = 0;
		c2[p[0]] = 0;
		for (int i = 1; i < n; ++i) {
			if (c[p[i]] == c[p[i - 1]] && c[nm(p[i] + (1 << k), n)] == c[nm(p[i - 1] + (1 << k), n)])
				c2[p[i]] = now;
			else
				c2[p[i]] = ++now;
		}
		memcpy(c, c2, sizeof(c));
		if (now + 1 >= n)
			break;
	}
	n -= 1;
}
int l;
int k;

int check(int x) {
	memset(en, 0, sizeof(en));
	for (int i = 0; i <= x; ++i) {
		if (p[i] + l <= n)
			en[p[i]] = 1;
	}
	for (int i = 0; i <= n; ++i)
		ans[i] = 1e9;
	ans[0] = 0;
	for (int i = 0; i < n; ++i) {
		if (l && i + (l - 1) <= n)
			ans[i + l - 1] = min(ans[i + l - 1], ans[i] + 1);
		if (en[i] && i + l <= n)
			ans[i + l] = min(ans[i + l], ans[i] + 1);
	}
	if (ans[n] <= k)
		return 1;
	else
		return 0;

}


int main() {
	scanf("%d", &k);
	scanf(" %s", s);
	n = strlen(s);
	sa();
	++k;
	l = (n + k - 1) / k;
	int lb = 0;
	int rb = n;
	while (rb - lb > 1) {
		int mid = (lb + rb) >> 1;
		if (check(mid))
			rb = mid;
		else
			lb = mid;
	}
	int st = p[rb];
	for (int i = 0; i < l; ++i)
		cout << s[st + i];
	return 0;
}

Submission Info

Compile Error

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

Judge Result