Submission #1016476

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

// O(N (log N)^2)
vector<int> suffix_array(string const & s){
	int n = s.length();
	vector<int> sa(n+1);
	vector<int> rank(n+1);
	
	for(int i=0;i<n+1;i++){
		sa[i] = i;
		rank[i] = i < n ? s[i] : -1;
	}
	
	auto rankf = [&](int i) { return i <= n ? rank[i] : -1; };
	vector<int> nxt(n+1);
	
	for(int k=1;k<=n;k<<=1){
		auto cmp = [&](int i, int j) { return make_pair(rank[i], rankf(i + k)) < make_pair(rank[j], rankf(j + k)); };
		sort(sa.begin(), sa.end(), cmp);
		nxt[sa[0]] = 0;
		
		for(int i=1;i<n+1;i++){
			nxt[sa[i]] = nxt[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
		}
		rank.swap(nxt);
	}
	
	return sa;
}


int main() {
	int k;
	string s;
	cin >> k >> s;
	vector<int> sa = suffix_array(s);
	vector<int> rank(sa.size());
	
	for(int i=0;i<sa.size();i++)
		rank[sa[i]] = i;
	
	int l = (s.length()+k) / (k+1);
	
	function<bool (int)> pred = [&](int a) {
		int used = 0;
		for(int i=0;i<s.length();++used){
			int delta = rank[i] < a ? l : l-1;
			if (delta == 0)
				return false;
			i += delta;
		}
		return used <= k+1;
	};
	
	int low = 0, high = rank.size();
	
	while (low + 1 < high){
		int mid = (low + high) / 2;
		(pred(mid) ? high : low) = mid;
	}
	
	int a = low;
	cout << s.substr(sa[a], l) << endl;
	return 0;
}

Submission Info

Judge Result