Submission #1007671


Source Code Expand

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

class SuffixArray {
	void CEB(vector<int> &v, vector<int> &b) {
		int vs = v.size(), bs = b.size();
		fill(b.begin(), b.end(), 0);
		for (int i = 0; i < vs; i++) b[v[i]]++;
		for (int i = 1; i < bs; i++) b[i] += b[i - 1];
	}
	void ISort(vector<int> &v, vector<int> &SA, int mv, vector<int> &b, vector<int> &isL) {
		int vs = v.size(), bs = b.size();
		fill(b.begin(), b.end(), 0);
		for (int i = 0; i < vs; i++) b[v[i]]++;
		int sum = 0;
		for (int i = 0; i < bs; i++) b[i] += sum, swap(sum, b[i]);
		for (int i = 0; i < vs; i++) {
			if (SA[i] > 0 && isL[SA[i] - 1]) SA[b[v[SA[i] - 1]]++] = SA[i] - 1;
		}
	}
	void IISort(vector<int> &v, vector<int> &SA, int mv, vector<int> &b, vector<int> &isL) {
		CEB(v, b);
		for (int i = v.size() - 1; i >= 0; i--) {
			if (SA[i] > 0 && !isL[SA[i] - 1]) SA[--b[v[SA[i] - 1]]] = SA[i] - 1;
		}
	}
	vector<int>SA_IS(vector<int> v, int mv) {
		int vs = v.size();
		if (vs == 1) return vector<int>(1, 0);
		vector<int> isL(vs), b(mv + 1), SA(vs, -1), ord(vs);
		auto isLMS = [&](int x)->bool { return x > 0 && isL[x - 1] && !isL[x]; };
		for (int i = vs - 2; i >= 0; i--) isL[i] = (v[i] > v[i + 1]) || (v[i] == v[i + 1] && isL[i + 1]);
		CEB(v, b);
		for (int i = 0; i < vs; i++) {
			if (isLMS(i)) SA[--b[v[i]]] = i;
		}
		ISort(v, SA, mv, b, isL);
		IISort(v, SA, mv, b, isL);
		int cur = 0;
		for (int i = 0; i < vs; i++) {
			if (isLMS(i)) ord[i] = cur++;
		}
		vector<int> nxv(cur);
		cur = -1;
		int prev = -1;
		for (int i = 0; i < vs; i++) {
			if (!isLMS(SA[i])) continue;
			bool diff = false;
			for (int d = 0; d < vs; d++) {
				if (prev == -1 || v[SA[i] + d] != v[prev + d] || isL[SA[i] + d] != isL[prev + d]) {
					diff = true;
					break;
				}
				else if (d && isLMS(SA[i] + d))break;
			}
			if (diff) cur++, prev = SA[i];
			nxv[ord[SA[i]]] = cur;
		}
		vector<int> reord(nxv.size());
		for (int i = 0; i < vs; i++) {
			if (isLMS(i)) reord[ord[i]] = i;
		}
		vector<int> nxSA = SA_IS(nxv, cur);
		CEB(v, b);
		for (int i = 0; i < SA.size(); i++) SA[i] = -1;
		for (int i = nxSA.size() - 1; i >= 0; i--) {
			SA[--b[v[reord[nxSA[i]]]]] = reord[nxSA[i]];
		}
		ISort(v, SA, mv, b, isL);
		IISort(v, SA, mv, b, isL);
		return SA;
	}
	vector<int>SA_IS(string s) {
		vector<int> v(s.size() + 1);
		for (int i = 0; i < s.size(); i++) v[i] = s[i] + 1;
		return SA_IS(v, *max_element(v.begin(), v.end()));
	}
	vector<int>construct_lcp(string &s, vector<int> &sa) {
		vector<int> lcp(s.size()), rank(s.size() + 1);
		int n = s.size(), h = 0;
		for (int i = 0; i <= n; i++) rank[sa[i]] = i;
		for (int i = 0; i < n; i++) {
			int j = sa[rank[i] - 1];
			if (h) h--;
			for (; j + h < n && i + h < n; h++) {
				if (s[j + h] != s[i + h]) break;
			}
			lcp[rank[i] - 1] = h;
		}
		return lcp;
	}
public:
	string s;
	vector<int> sa, lcp;
	void init(string &T) {
		s = T;
		sa = SA_IS(s);
		lcp = construct_lcp(s, sa);
	}
	SuffixArray(string &t) { init(t); }
	SuffixArray() {}
	bool contain(string &t) {
		int a = 0, b = s.size();
		while (b - a > 1) {
			int c = (a + b) / 2;
			if (s.compare(sa[c], t.size(), t) < 0) a = c;
			else b = c;
		}
		return !s.compare(sa[b], t.size(), t);
	}
};

string s; int n, x;
int main() {
	cin >> x >> s; n = s.size();
	int quot = n / (x + 1);
	if (n % (x + 1) == 0) {
		string ret = "";
		for (int i = 0; i < n; i += quot) ret = max(ret, s.substr(i, quot));
		cout << ret << endl;
	}
	else {
		SuffixArray Q(s);
		vector<int> sa = Q.sa;
		vector<int> sa_inverse(n + 1);
		for (int i = 0; i < n + 1; i++) sa_inverse[sa[i]] = i;
		vector<int> dp;
		function<int(int)> solve = [&](int t) {
			dp = vector<int>(n + 1, 999999999); dp[0] = 0;
			for (int i = quot; i <= n; i++) {
				dp[i] = min(dp[i], dp[i - quot] + 1);
				if (i != quot && sa_inverse[i - quot - 1] < t) dp[i] = min(dp[i], dp[i - quot - 1] + 1);
			}
			return dp[n];
		};
		int l = 0, r = n + 1;
		while (r - l > 1) {
			int m = (l + r) / 2;
			if (solve(m) <= x + 1) r = m;
			else l = m;
		}
		cout << s.substr(sa[l], quot + 1) << endl;
	}
	return 0;
}

Submission Info

Submission Time
Task B - Problem where Commas Separate Digits
User square1001
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 4270 Byte
Status AC
Exec Time 33 ms
Memory 3584 KB

Judge Result

Set Name Sample Dataset1 Dataset2 Dataset3 Dataset4 Dataset5
Score / Max Score 0 / 0 100 / 100 100 / 100 200 / 200 200 / 200 400 / 400
Status
AC × 3
AC × 17
AC × 32
AC × 49
AC × 64
AC × 79
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 3 ms 256 KB
subtask_01_02.txt AC 3 ms 256 KB
subtask_01_03.txt AC 3 ms 256 KB
subtask_01_04.txt AC 3 ms 256 KB
subtask_01_05.txt AC 3 ms 256 KB
subtask_01_06.txt AC 3 ms 256 KB
subtask_01_07.txt AC 3 ms 256 KB
subtask_01_08.txt AC 3 ms 256 KB
subtask_01_09.txt AC 3 ms 256 KB
subtask_01_10.txt AC 3 ms 256 KB
subtask_01_11.txt AC 3 ms 256 KB
subtask_01_12.txt AC 3 ms 256 KB
subtask_01_13.txt AC 3 ms 256 KB
subtask_01_14.txt AC 3 ms 256 KB
subtask_01_15.txt AC 3 ms 256 KB
subtask_01_16.txt AC 3 ms 256 KB
subtask_01_17.txt AC 3 ms 256 KB
subtask_02_01.txt AC 3 ms 256 KB
subtask_02_02.txt AC 3 ms 256 KB
subtask_02_03.txt AC 3 ms 256 KB
subtask_02_04.txt AC 3 ms 256 KB
subtask_02_05.txt AC 3 ms 256 KB
subtask_02_06.txt AC 3 ms 256 KB
subtask_02_07.txt AC 3 ms 256 KB
subtask_02_08.txt AC 3 ms 256 KB
subtask_02_09.txt AC 3 ms 256 KB
subtask_02_10.txt AC 3 ms 256 KB
subtask_02_11.txt AC 3 ms 256 KB
subtask_02_12.txt AC 3 ms 256 KB
subtask_02_13.txt AC 3 ms 256 KB
subtask_02_14.txt AC 3 ms 256 KB
subtask_02_ex1.txt AC 3 ms 256 KB
subtask_03_01.txt AC 4 ms 256 KB
subtask_03_02.txt AC 3 ms 256 KB
subtask_03_03.txt AC 3 ms 256 KB
subtask_03_04.txt AC 3 ms 256 KB
subtask_03_05.txt AC 3 ms 256 KB
subtask_03_06.txt AC 3 ms 256 KB
subtask_03_07.txt AC 3 ms 256 KB
subtask_03_08.txt AC 3 ms 256 KB
subtask_03_09.txt AC 3 ms 256 KB
subtask_03_10.txt AC 3 ms 256 KB
subtask_03_11.txt AC 3 ms 256 KB
subtask_03_12.txt AC 3 ms 256 KB
subtask_03_13.txt AC 3 ms 256 KB
subtask_03_14.txt AC 3 ms 256 KB
subtask_03_15.txt AC 3 ms 256 KB
subtask_03_ex2.txt AC 3 ms 256 KB
subtask_03_ex3.txt AC 3 ms 256 KB
subtask_04_01.txt AC 3 ms 256 KB
subtask_04_02.txt AC 3 ms 256 KB
subtask_04_03.txt AC 3 ms 256 KB
subtask_04_04.txt AC 3 ms 256 KB
subtask_04_05.txt AC 3 ms 384 KB
subtask_04_06.txt AC 3 ms 256 KB
subtask_04_07.txt AC 3 ms 256 KB
subtask_04_08.txt AC 3 ms 256 KB
subtask_04_09.txt AC 3 ms 256 KB
subtask_04_10.txt AC 3 ms 256 KB
subtask_04_11.txt AC 3 ms 256 KB
subtask_04_12.txt AC 3 ms 256 KB
subtask_04_13.txt AC 3 ms 256 KB
subtask_04_14.txt AC 3 ms 256 KB
subtask_04_15.txt AC 3 ms 256 KB
subtask_05_01.txt AC 30 ms 3584 KB
subtask_05_02.txt AC 33 ms 3584 KB
subtask_05_03.txt AC 11 ms 512 KB
subtask_05_04.txt AC 9 ms 512 KB
subtask_05_05.txt AC 31 ms 3584 KB
subtask_05_06.txt AC 8 ms 512 KB
subtask_05_07.txt AC 7 ms 512 KB
subtask_05_08.txt AC 6 ms 512 KB
subtask_05_09.txt AC 6 ms 512 KB
subtask_05_10.txt AC 30 ms 3328 KB
subtask_05_11.txt AC 21 ms 2784 KB
subtask_05_12.txt AC 21 ms 2784 KB
subtask_05_13.txt AC 24 ms 2816 KB
subtask_05_14.txt AC 29 ms 3328 KB
subtask_05_15.txt AC 15 ms 1664 KB