Submission #1158028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158028		alexander707070	Ancient Machine 2 (JOI23_ancient2)	C++20	97 / 100	33 ms	684 KiB

ancient2

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

using namespace std;


namespace {

    int n,sz;
    int variable_example = 1;

}  // namespace

struct equation{
    bitset<1000> coefs;
    int res;

    inline friend equation operator + (equation fr,equation sc){
        return {fr.coefs^sc.coefs,fr.res^sc.res};
    }
}e[1000];

bitset<1000> bit[1000];

bool expres(bitset<1000> s){
    for(int i=0;i<1000;i++){
        if(s[i]==1)s^=bit[i];
    }

    return s.count()==0;
}

void add(bitset<1000> s){

    for(int i=0;i<1000;i++){
        if(s[i]==1 and bit[i][i]==0){
            bit[i]=s; break;
        }else if(s[i]==1){
            s^=bit[i];
        }
    }
}

int ask(int q,int p){
    vector<int> a,b;

    for(int i=0;i<p;i++){
        for(int f=0;f<2;f++){
            if(i!=q){
                a.push_back(((i+1)%p)*2+f);
                b.push_back(((i+1)%p)*2+f);
            }else{
                a.push_back(((i+1)%p)*2+f);
                b.push_back(((i+1)%p)*2+(f^1));
            }
        }
    }

    int m=2*p;
    int state=Query(m,a,b);
    return state%2;
}

int value[1000];

void solve_system(){
    for(int i=0;i<n;i++){
        int pivot=-1;

        for(int f=i;f<n;f++){
            if(e[f].coefs[i]==1){
                pivot=f; break;
            }
        }

        swap(e[i],e[pivot]);

        for(int f=i+1;f<n;f++){
            if(e[f].coefs[i]==1)e[f]=e[f]+e[i];
        }
    }

    for(int i=n-1;i>=0;i--){
        value[i]=e[i].res;

        for(int k=n-1;k>i;k--){
            if(e[i].coefs[k]==1)value[i]^=value[k];
        }
    }
}

string Solve(int N) {
    n=N;

    for(int i=1;i<60;i++){
        for(int f=0;f<i;f++){
            bitset<1000> curr;

            for(int k=0;k*i+f<n;k++){
                curr[k*i+f]=1;
            }

            if(!expres(curr)){
                e[sz]={curr,ask(f,i)}; sz++;

                add(curr);
            }
        }
    }

    solve_system();

    string ans;
    for(int i=0;i<n;i++)ans.push_back(value[i]+'0');

    return ans;
}

• Subtask 1: 97 / 100