#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 1000;
bitset<M> bs[M], iv[M];
int sz = 0, val[M], tt[M];
vector<array<int, 2>> vec;
void add(bitset<M> &x, int k, int r) {
bitset<M> t;
for (int i = 0; i < M; i++) {
if (bs[i][i] == 0 || x[i] == 0)
continue;
x ^= bs[i];
t ^= iv[i];
}
if (x.count() == 0) return;
sz++;
int pos = x._Find_first();
bs[pos] = x;
iv[pos] = t;
iv[pos][vec.size()] = 1;
vec.push_back({k, r});
}
string build() {
for (int i = 0; i < M; i++) {
tt[i] = 0;
for (int j = 0; j < M; j++)
if (iv[i][j]) tt[i] ^= val[j];
}
string s;
for (int i = 0; i < M; i++) {
int xx = tt[i];
for (int j = i + 1; j < M; j++) {
if (bs[i][j] == 0) continue;
bs[i] ^= bs[j];
xx ^= tt[j];
}
s.push_back(xx + '0');
}
return s;
}
string Solve(int N) {
const int len = 108;
return "";
for (int i = 1; i <= len - 2; i++) {
bitset<M> cur;
for (int j = 0; j < M; j++)
cur[j] = (j == i - 1);
add(cur, -1, i);
}
return "";
for (int i = 1; i <= len / 2; i++) {
for (int k = 0; k < i; k++) {
bitset<M> cur;
for (int j = 0; j < M; j++)
cur[j] = (j % i == k);
add(cur, i, k);
}
}
return "";
assert(sz == M);
assert(sz == (int) vec.size());
for (int i = 0; i < M; i++) {
auto [k, r] = vec[i];
if (k == -1) {
vector<int> a, b;
for (int j = 0; j < r; j++) {
a.push_back(j + 1);
b.push_back(j + 1);
}
b.back() = r + 1;
a.push_back(r);
b.push_back(r);
a.push_back(r + 1);
b.push_back(r + 1);
val[i] = Query(a.size(), a, b) - r;
} else {
vector<int> a(2 * k), b(2 * k);
for (int i = 0; i < k; i++) {
int j = (i + 1) % k;
for (int t = 0; t < 2; t++) {
a[2 * i + t] = 2 * j + t;
if (i != r) {
b[2 * i + t] = 2 * j + t;
} else {
b[2 * i + t] = 2 * j + 1 - t;
}
}
}
val[i] = Query(a.size(), a, b) % 2;
}
}
return build();
}
/*
namespace {
using std::exit;
using std::fprintf;
using std::printf;
using std::scanf;
constexpr int N_MAX = 1'000;
constexpr int M_MAX = 1'002;
constexpr int Q_MAX = 1'000;
int N;
char S[N_MAX + 1];
int query_count = 0;
int query_m_max = 0;
void WrongAnswer(int code) {
printf("Wrong Answer [%d]\n", code);
exit(0);
}
} // namespace
int Query(int m, std::vector<int> a, std::vector<int> b) {
if (++query_count > Q_MAX) WrongAnswer(7);
if (!(1 <= m && m <= M_MAX)) WrongAnswer(4);
if ((int)a.size() != m || (int)b.size() != m) WrongAnswer(5);
for (int i = 0; i < m; i++) {
if (!(0 <= a[i] && a[i] <= m - 1) || !(0 <= b[i] && b[i] <= m - 1))
WrongAnswer(6);
}
if (m > query_m_max) query_m_max = m;
int memory = 0;
for (int i = 0; i < N; i++) {
if (S[i] == '0') {
memory = a[memory];
}
if (S[i] == '1') {
memory = b[memory];
}
}
return memory;
}
int main() {
if (scanf("%d", &N) != 1) {
fprintf(stderr, "Error while reading input.\n");
exit(1);
}
if (scanf("%s", S) != 1) {
fprintf(stderr, "Error while reading input.\n");
exit(1);
}
std::string s = Solve(N);
if ((int)s.size() != N) WrongAnswer(1);
for (int i = 0; i < N; i++) {
if (!(s[i] == '0' || s[i] == '1')) WrongAnswer(2);
}
for (int i = 0; i < N; i++) {
if (s[i] != S[i]) WrongAnswer(3);
}
printf("Accepted: %d\n", query_m_max);
return 0;
}
//*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |