oj.uz

Submission #168376

# Submission time Handle Problem Language Result Execution time Memory
168376 2019-12-12T20:23:25 Z Thuleanx Periodicity (POI11_okr) C++14
0 / 100
 67 ms 16936 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+7;

vector<int> extract(char s[], int n) {
	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;
	scanf("%d", &t);
	stringstream ss;
	char s[N];
	while (t--) {
		scanf("%s", s);
		int n = string(s).length();
		vector<int> p = extract(s,n); // all borders are here		

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

	return 0;
}

Compilation message

okr.cpp: In function 'int main()':
okr.cpp:47:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < p.size(); i++) {
                   ~~^~~~~~~~~~
okr.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &t);
  ~~~~~^~~~~~~~~~
okr.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
   ~~~~~^~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 16936 KB Output isn't correct