## Submission #168379

# Submission time Handle Problem Language Result Execution time Memory
168379 2019-12-12T20:45:00 Z Thuleanx Periodicity (POI11_okr) C++14
100 / 100
69 ms 17884 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+2*p[i-1]-p[i], sizeof(char)*(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 16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 428 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

#### Subtask #2 16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 352 KB Output is correct

#### Subtask #3 17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

#### Subtask #4 17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 404 KB Output is correct
2 Correct 14 ms 4688 KB Output is correct

#### Subtask #5 17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct

#### Subtask #6 17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 17884 KB Output is correct