Submission #812530

#TimeUsernameProblemLanguageResultExecution timeMemory
812530piOOEAncient Machine 2 (JOI23_ancient2)C++17
100 / 100
87 ms764 KiB
#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; 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; bitset<maxN> b{}; b[i] = 1, b[n] = ans[i]; insert(b); } mt19937 rnd(228); while (Q < 1000 && basisSize < n) { constexpr int R = 51; int p = rnd() % R + 1, q = rnd() % p; bitset<maxN> b{}; for (int i = q; i < n; i += p) { b[i] = 1; } if (query(b) == -1) { b[n] = findXor(p, q); insert(b); } } 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) { s[i] = '0' + ans[i]; } return s; }
#Verdict Execution timeMemoryGrader output
Fetching results...