#include "ancient2.h"
#include <bits/stdc++.h>
#define MAX_N 1000
#define M_UPPERBOUND 102
using bitvec = std::bitset<MAX_N>;
struct basis_manager {
std::vector<std::pair<int, bitvec> > basis;
bool add(bitvec v) {
for (auto i : basis) if (v[i.first]) v ^= i.second;
if (v.any()) {
basis.push_back({v._Find_first(), v});
return true;
}
return false;
}
};
// {mod, remainder, actual 01 vector}
// {-1, i, actual 01 vector} : i-th
// {-2, i, actual 01 vector} : i-th from the back
std::vector<std::tuple<int, int, bitvec> > list_needed_vecs(int n) {
std::vector<std::vector<std::tuple<int, int, bitvec> > > cands(M_UPPERBOUND + 1);
// periodic
for (int mod = 1; mod <= M_UPPERBOUND / 2; mod++) {
for (int rem = 0; rem < mod; rem++) {
bitvec x;
for (int i = rem; i < n; i += mod) x[i] = 1;
cands[2 * mod].push_back(std::make_tuple(mod, rem, x));
}
}
// prefix
for (int i = 0; i + 3 <= M_UPPERBOUND; i++) {
bitvec x;
x[i] = 1;
cands[i + 3].push_back(std::make_tuple(-1, i, x));
}
// suffix
for (int i = 0; i + 2 <= M_UPPERBOUND; i++) {
bitvec x;
x[n - 1 - i] = 1;
cands[i + 2].push_back({-2, i, x});
}
basis_manager basis;
std::vector<std::tuple<int, int, bitvec> > res;
for (int i = 0; i <= M_UPPERBOUND; i++) {
for (auto j : cands[i]) {
if (basis.add(std::get<2>(j))) res.push_back(j);
if ((int) basis.basis.size() == n) break;
}
if ((int) basis.basis.size() == n) break;
}
return res;
}
std::vector<bool> solve_linear_equation(std::vector<bitvec> &a, std::vector<bool> &b) {
int n = a.size();
for (int i = 0; i < n; i++) {
int id = -1;
for (int j = i; j < n; j++) if (a[j][i]) { id = j; break; }
assert(id != -1);
std::swap(a[i], a[id]);
swap(b[i], b[id]);
for (int j = 0; j < n; j++) if (j != i && a[j][i]) a[j] ^= a[i], b[j] = b[j] ^ b[i];
}
return b;
}
std::string Solve(int n) {
auto list = list_needed_vecs(n);
std::vector<bitvec> mat;
std::vector<bool> res;
std::vector<bool> back_res;
for (auto i : list) {
int mod = std::get<0>(i);
int rem = std::get<1>(i);
auto query_mod = [&] () {
int m = mod * 2;
std::vector<int> a(m), b(m);
for (int j = 0; j < mod; j++) {
int next = (j + 1) % mod;
a[j] = b[j] = next;
a[j + mod] = b[j + mod] = next + mod;
if (j == rem) std::swap(b[j], b[j + mod]);
}
return Query(m, a, b) >= mod;
};
auto query_forward = [&] () {
int m = rem + 3 + 3;
std::vector<int> a(m), b(m);
for (int j = 0; j < rem + 3; j++) a[j] = b[j] = j + 1;
a[rem + 3] = rem + 1 + 3;
b[rem + 3] = rem + 2 + 3;
a[rem + 1 + 3] = b[rem + 3 + 1] = rem + 3 + 1;
a[rem + 2 + 3] = b[rem + 3 + 2] = rem + 3 + 2;
return Query(m, a, b) == rem + 2 + 3;
};
auto query_back = [&] () {
assert(rem == (int) back_res.size());
back_res.insert(back_res.begin(), 0);
int m = rem + 2;
std::vector<int> a(m), b(m);
for (int i = 0; i <= rem + 1; i++) {
auto get = [&] (bool next) {
auto cur = std::vector<bool>(back_res.begin(), back_res.begin() + i);
cur.push_back(next);
for (int j = std::min(rem + 1, i + 1); j; j--)
if (std::vector<bool>(cur.end() - j, cur.end()) ==
std::vector<bool>(back_res.begin(), back_res.begin() + j)) return j;
return 0;
};
a[i] = get(0);
b[i] = get(1);
}
bool res = Query(m, a, b) != rem + 1;
back_res[0] = res;
return res;
};
mat.push_back(std::get<2>(i));
res.push_back(mod >= 1 ? query_mod() : mod == -1 ? query_forward() : query_back());
}
res = solve_linear_equation(mat, res);
std::string res_str;
for (auto i : res) res_str.push_back('0' + i);
return res_str;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
848 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
