# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
812442 | piOOE | Ancient Machine 2 (JOI23_ancient2) | C++17 | 10 ms | 348 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
constexpr int maxN = 1001;
int n, Q = 0, basisSize = 0;
bool findPrefixBit(int m) { // 0 indexed
vector<int> a(m + 3), b(m + 3);
for (int i = 0; i < m; ++i) {
a[i] = b[i] = i + 1;
}
a[m + 1] = b[m + 1] = m + 1;
a[m + 2] = b[m + 2] = m + 2;
a[m] = m + 1, b[m] = m + 2;
Q += 1;
return Query(size(a), a, b) == m + 2;
}
int findLongestPrefix(const string &s, const string &t) {
for (int len = min(size(s), size(t)); len > 0; --len) {
if (s.substr(0, len) == t.substr(size(t) - len)) {
return len;
}
}
return 0;
}
bool findSuffixBit(int m, string suf) { // find m-th last bit (1 indexed, i.e. the last char is the 1st)
suf = '1' + suf;
vector<int> a(m + 1), b(m + 1);
a[m] = b[m] = m;
for (int i = 0; i <= m; ++i) {
string sa = suf.substr(0, i) + '0';
string sb = suf.substr(0, i) + '1';
a[i] = findLongestPrefix(suf, sa);
b[i] = findLongestPrefix(suf, sb);
}
Q += 1;
return Query(m + 1, a, b) == m;
}
bitset<maxN> basis[maxN];
int query(bitset<maxN> a) {
for (int i = 0; i < n; ++i) {
if (!a[i]) {
continue;
}
if (basis[i].none()) {
return -1;
}
a ^= basis[i];
}
return a[n];
}
bool insert(bitset<maxN> a) {
for (int i = 0; i < n; ++i) {
if (!a[i]) {
continue;
}
if (basis[i].none()) {
basis[i] = a;
basisSize += 1;
return true;
}
a ^= basis[i];
}
return false;
}
int findXor(int p, int q) { // finds xor of s[x] (x = q + p * k)
int m = p * 2;
vector<int> a(m);
iota(a.begin(), a.end(), 1), iota(a.begin() + p, a.end(), p + 1);
a[p - 1] = 0, a[m - 1] = p;
vector<int> b = a;
b[q] += p, b[q + p] -= p;
Q += 1;
assert(*max_element(a.begin(), a.end()) < 2 * m && *max_element(b.begin(), b.end()) < 2 * m);
assert(*min_element(a.begin(), a.end()) >= 0 && *min_element(b.begin(), b.end()) >= 0);
return Query(m, a, b) >= p;
}
} // namespace
std::string Solve(int N) {
n = N;
constexpr int M = 100;
vector<int> ans(n, -1);
for (int i = 0; i < min(n, M); ++i) {
ans[i] = findPrefixBit(i);
bitset<maxN> b{};
b[i] = 1, b[n] = ans[i];
insert(b);
}
string suf;
for (int i = n - 1; i >= max(n - M, M); --i) {
ans[i] = findSuffixBit(n - i, suf);
suf = char('0' + ans[i]) + suf;
}
mt19937 rnd(228);
while (Q < 1000 && basisSize < n) {
Q += 1;
while (basisSize < n) {
constexpr int R = 228;
int p = rnd() % R + 1, q = rnd() % R;
bitset<maxN> b{};
for (int i = q; i < n; i += p) {
b[i] = 1;
}
if (query(b) == -1) {
b[n] = findXor(p, q);
assert(insert(b));
break;
}
}
}
for (int i = M; i + M < n; ++i) {
bitset<maxN> b{};
b[i] = 1;
ans[i] = query(b);
}
string s(n, '?');
for (int i = 0; i < n; ++i) {
assert(ans[i] != -1);
s[i] = '0' + ans[i];
}
return s;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |