Submission #1260833

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

ancient2

#include "ancient2.h"

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

int BASIS[][3] = {
    {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}
};

int Xor(int n, int o) {
    int m = n+n;
    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;

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

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

    return r >= n;
}

string solve(int N, vector<bitset<1001>>& BS) {
    assert(N==1000);
    int ii = 0;
    for (auto& [s, e, n] : BASIS) {
        for (int o = s; o <= e; ++o) {
            BS[ii].reset();
            for (int i = 0; i * n + o < 1000; ++i) {
                BS[ii].set(i*n+o);
            }
            int a = Xor(n, o);
            if (a) BS[ii].set(1000);
            ++ii;
        }
    }
    
    vector where(1000, -1);
    vector ans(1000, 0);
    for (int c = 0, r = 0; c < 1000 && r < 1000; ++c) {
        for (int i = r; i < 1000; ++i) {
            if (BS[i][c]) {
                swap(BS[i], BS[r]);
                break;
            }
        }
        if (!BS[r][c]) continue;
        where[c] = r;

        for (int i = 0; i < 1000; ++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;
    }

    string anss(N, '0');
    for (int i = 0; i < 1000; ++i) {
        if (ans[i]) anss[i] = '1';
    }

    return anss;
}

string Solve(int N) {
    vector<bitset<1001>> BS(1000);
    return solve(N, BS);
}

• Subtask 1: 0 / 100