#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'
const int N = 1000, LB = 100, UB = 898;
bitset<N> basisx[N], basisy[N];
bool res[N], val[N];
vector<pair<int, int>> pairs;
void try_add(int q, int p){
bitset<N> curx, cury;
for (int i = q; i < N; i += p) curx.set(i);
for (int i = UB; i >= LB; i--){
if (!curx.test(i)) continue;
if (!basisx[i].any()){
cury.set(sz(pairs));
pairs.pb({q, p});
basisx[i] = curx, basisy[i] = cury;
return;
}
curx ^= basisx[i], cury ^= basisy[i];
}
}
void precalc(){
for (int p = 1;; p++){
for (int q = 0; q < p; q++){
try_add(q, p);
if (sz(pairs) == UB - LB + 1) return;
}
}
}
vector<int> prefix_function(string s){
int n = sz(s);
vector<int> pi(n);
for (int i = 1; i < n; i++){
int k = pi[i - 1];
while (k && s[k] != s[i]) k = pi[k - 1];
pi[i] = k + (s[i] == s[k]);
}
return pi;
}
vector<vector<int>> build_automaton(string s){
auto pi = prefix_function(s);
int n = sz(s);
vector<vector<int>> aut(2, vector<int>(n + 1));
for (int i = 0; i <= n; i++){
for (int c = 0; c < 2; c++){
if (s[i] == '0' + c) aut[c][i] = i + 1;
else if (i) aut[c][i] = aut[c][pi[i - 1]];
}
}
return aut;
}
std::string Solve(int n) {
precalc();
for (int i = 0; i < sz(pairs); i++){
auto [q, p] = pairs[i];
vector<int> a(2 * p), b(2 * p);
iota(all(a), 1);
iota(all(b), 1);
a[p - 1] = 0, a[2 * p - 1] = p;
b[p - 1] = 0, b[2 * p - 1] = p;
b[q] = p + (q + 1) % p, b[p + q] = (q + 1) % p;
res[i] = (Query(2 * p, a, b) >= p);
}
string s, t;
for (int i = 0; i < LB; i++){
vector<int> a(i + 3), b(i + 3);
iota(all(a), 1);
iota(all(b), 1);
a[i] = i + 1, b[i] = i + 2;
a[i + 1] = b[i + 1] = i + 1;
a[i + 2] = b[i + 2] = i + 2;
s.pb(Query(sz(a), a, b) == i + 1? '0' : '1');
}
for (int i = 0; i < 999 - UB; i++){
auto aut = build_automaton("0" + t);
t = (Query(sz(aut[0]), aut[0], aut[1]) == sz(t) + 1? "0" : "1") + t;
}
string u;
for (int i = LB; i <= UB; i++){
for (int j = 0; j < sz(pairs); j++){
if (basisy[i].test(j)) val[i] ^= res[j];
}
for (int j = LB; j < i; j++){
if (basisx[i].test(j)) val[i] ^= val[j];
}
u.pb('0' + val[i]);
}
return s + u + t;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
532 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
