Submission #812446

#	Time	Username	Problem	Language	Result	Execution time	Memory
812446		piOOE	Ancient Machine 2 (JOI23_ancient2)	C++17	0 / 100	13 ms	336 KiB

ancient2

#include "ancient2.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    constexpr int maxN = 1001;
    int n, Q = 0, basisSize = 0;

    void check(const vector<int> &a) {
        assert(*max_element(a.begin(), a.end()) < size(a));
        assert(*min_element(a.begin(), a.end()) >= 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;
        check(a), check(b);
        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;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from ancient2.cpp:2:
ancient2.cpp: In function 'void {anonymous}::check(const std::vector<int>&)':
ancient2.cpp:11:49: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         assert(*max_element(a.begin(), a.end()) < size(a));
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

• Subtask 1: 0 / 100