Submission #1260629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260629		ncosiaafo	Ancient Machine 2 (JOI23_ancient2)	C++20	0 / 100	0 ms	320 KiB

ancient2

#include "ancient2.h"

#include<bits/stdc++.h>

namespace {

int variable_example = 1;
std::vector<std::array<int, 3>> basis = {
    {0,0,1}, {0,0,2}, {0,1,3}, {0,1,4}, {0,3,5}, {0,1,6}, {0,5,7}, {0,3,8}, {0,5,9}, {0,3,10}, {0,9,11}, {0,3,12}, {0,11,13}, {0,5,14}, {0,7,15}, {0,7,16}, {0,15,17}, {0,5,18}, {0,17,19}, {0,7,20}, {0,11,21}, {0,9,22}, {0,21,23}, {0,7,24}, {0,19,25}, {0,11,26}, {0,17,27}, {0,11,28}, {0,27,29}, {0,7,30}, {0,29,31}, {0,15,32}, {0,19,33}, {0,15,34}, {0,23,35}, {0,11,36}, {0,35,37}, {0,17,38}, {0,23,39}, {0,15,40}, {0,39,41}, {0,11,42}, {0,41,43}, {0,19,44}, {0,23,45}, {0,21,46}, {0,45,47}, {0,15,48}, {0,41,49}, {0,19,50}, {0,31,51}, {0,23,52}, {0,51,53}, {0,17,54}, {0,39,55}, {0,23,56}, {0,30,57}, {0,3,58}, {6,6,58}
};

std::vector<std::bitset<1001>> bs;


}  // namespace




int Xor(int n, int o) {
    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) {
    for (auto& [s, e, n] : basis) {
        for (int o = s; o <= e; ++o) {
            bs.emplace_back(std::bitset<1001>(0));
            bs.back().reset();
            for (int i = 0; i * n + o < 1000; ++i) {
                bs.back().set(i*n+o);
            }
            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]) {
                std::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];
        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