Submission #168373

#	Time	Username	Problem	Language	Result	Execution time	Memory
168373		Thuleanx	Periodicity (POI11_okr)	C++14	66 / 100	1089 ms	6260 KiB

okr

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

vector<int> extract(string s) {
	int n = s.length();
	vector<int> pi(n);
	pi[0] = 0;
	for (int i = 1; i < n; i++) {
		int j = pi[i-1];
		while (j > 0 && s[i] != s[j])
			j = pi[j-1];
		if (s[i] == s[j])
			j++;
		pi[i] = j;
	}
	vector<int> borders;
	int j = n;
	while (j>0) {
		borders.push_back(j);
		j = pi[j-1];
	}
	reverse(begin(borders), end(borders));
	return borders;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t; cin>>t;
	stringstream ss;
	while (t--) {
		string s; cin>>s;
		vector<int> p = extract(s); // all borders are here		

		// get seed
		string ans;
		if (p[0] == 1)
			ans.push_back('0');
		else for (int i = 0; i < p[0]; i++)
			ans.push_back('0'+(i==p[0]-1));
		
		for (int i = 1; i < p.size(); i++) {
			if (p[i] - 2*p[i-1] <= 0) {
				ans = ans.substr(0, p[i]-p[i-1]) + ans;
			} else {
				for (int j = 0; j < p[i]-2*p[i-1]; j++)
					ans.push_back('0');
				ans = ans + ans.substr(0,p[i-1]);
				vector<int> border_now = extract(ans); // O(N) but runs only O(\log{n}) time and O(1) amortized
				if (!equal(begin(p), begin(p)+i+1, begin(border_now)))
					ans[p[i]-p[i-1]-1] = '1';
			}
		}
		ss << ans << endl;
	}
	cout << ss.str();

	return 0;
}

Compilation message (stderr)

okr.cpp: In function 'int main()':
okr.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < p.size(); i++) {
                   ~~^~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 17
• Subtask 5: 17 / 17
• Subtask 6: 0 / 17