Submission #1261053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261053		ncosiaafo	Ancient Machine 2 (JOI23_ancient2)	C++17	0 / 100	0 ms	352 KiB

ancient2

#include "ancient2.h"

#include<bits/stdc++.h>
using namespace std;

namespace {

int variable_example = 1;



}  // namespace

// this is AI gen
vector<pair<int,int>> find_basis() {
    const int N = 1000, MAXL = 57;
    using Vec = bitset<N>;

    // generate candidates
    vector<pair<int,int>> candidates;
    vector<Vec> candMask;
    for (int L = 1; L <= MAXL; L++) {
        for (int o = 0; o < L; o++) {
            Vec v;
            for (int p = o; p < N; p += L) v.set(p);
            candidates.push_back({o, L});
            candMask.push_back(v);
        }
    }

    // shuffle
    mt19937 g(42);
    vector<int> order(candidates.size());
    iota(order.begin(), order.end(), 0);
    shuffle(order.begin(), order.end(), g);

    // Gaussian elimination greedy
    vector<pair<int,int>> chosen;
    vector<Vec> basis(N); // basis vectors by pivot
    for (int idx : order) {
        Vec v = candMask[idx];
        // reduce against current basis
        for (int i = N-1; i >= 0; i--) {
            if (v[i]) {
                if (basis[i].any()) v ^= basis[i];
                else {
                    basis[i] = v;
                    chosen.push_back(candidates[idx]);
                    break;
                }
            }
        }
        if ((int)chosen.size() == N) break;
    }

    // final check: did we get 1000 independent vectors?
    if ((int)chosen.size() != N) chosen.clear();
    return chosen;
}



// these not
int Xor(int n, int o) {
    assert(o<n);
    int m = n+n;
    std::vector<int> a(m), b(m);
    for (int i = 0; i < n; ++i) {
        a[i] = i+1;
        b[i] = i+1;
    }
    a[n-1] = 0; b[n-1] = 0;
    for (int i = n; i < m; ++i) {
        a[i] = i+1;
        b[i] = i+1;
    }
    a[m-1] = n; b[m-1] = n;

    std::swap(b[o], b[o+n]);

    int r = Query(m, a, b);

    return r >= n;
}

std::string Solve(int N) {
    assert(1000==N);
    std::vector<std::pair<int,int>> basis = find_basis();
    std::vector<std::bitset<1001>> bs;
    for (auto& [o, n] : basis) {
        bs.emplace_back(std::bitset<1001>(0));
        bs.back().reset();
        for (int i = o; i < 1000; i += n) {
            bs.back().set(i);
        }
        int a = Xor(n, o);
        if (a) bs.back().set(1000);
    }
    
    std::vector where(1000, -1);
    std::vector ans(1000, 0);
    for (int c = 0, r = 0; c < 1000 && r < bs.size(); ++c) {
        for (int i = r; i < bs.size(); ++i) {
            if (bs[i][c]) {
                swap(bs[i], bs[r]);
                break;
            }
        }
        if (!bs[r][c]) continue;
        where[c] = r;

        for (int i = 0; i < bs.size(); ++i) {
            if (i != r && bs[i][c]) bs[i] ^= bs[r];
        }
        ++r;
    }

    for (int i = 0; i < 1000; ++i) {
        if (where[i] == -1) continue;
        int r = where[i];
        assert(0 <= r && r < bs.size());
        if (bs[r].count() == 2) ans[i] = 1;
    }

    std::string s = "";
    for (int i = 0; i < 1000; ++i) {
        if (ans[i]) s += "1";
        else s += "0";
    }

    return s;
}

• Subtask 1: 0 / 100