Submission #1216105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216105		lighton	Ancient Machine 2 (JOI23_ancient2)	C++20	100 / 100	25 ms	520 KiB

ancient2

#include "ancient2.h"

#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
const int N = 1000;
string ans;

void go(int n){
    vector<int> A(n+2), B(n+2);
    forf(i,0,n-1) A[i] = i+1,B[i] = i+1;
    A[n-1] = n, B[n-1] =n+1;
    A[n] = n, B[n] = n, A[n+1] = n+1, B[n+1] = n+1;
    if(Query(sz(A),A,B) == n) ans[n-1] = '0';
    else ans[n-1] = '1';
}
void go2(int s){
    ans[s] = '0';
    string t; forf(i,s,N-1) t.pb(ans[i]);
    int n = sz(t); t.pb('-');
    vector<int> A(n+1), B(n+1);

    forf(i,0,n){
        int l = min(n,i+1);
        while(l){
            string tmp = t.substr(i+1-l,l-1) + '0';
            if(t.substr(0,l) == tmp) break;
            l--;
        }
        A[i] = l;

        l = min(n,i+1);
        while(l){
            string tmp = t.substr(i+1-l,l-1) + '1';

            if(t.substr(0,l) == tmp) break;
            l--;
        }
        B[i] = l;
    }

    if(Query(sz(A),A,B) != n) ans[s] = '1';
}

bool cyc(int p, int q){
    vector<int> A(2*p), B(2*p);
    forf(i,0,p-1) A[i] = (i+1)%p, B[i] = (i+1)%p,
                A[i+p] = p+(i+1)%p, B[i+p] = p+(i+1)%p;
    B[q] = p+(q+1)%p; B[p+q] = (q+1)%p;

    return (Query(sz(A),A,B) >= p);
}

const int s = 100, e = 900;
void solve(){
    const int n = e-s+1;
    vector<bitset<n+1> > mat(n,bitset<n+1>(0));
    int cnt = 0;
    forf(i,1,100) forf(j,0,i-1){
        if(cnt == n) break;
        bitset<n+1> tmp(0);
        forf(k,s,e) if(k%i == j) tmp[k-s]=true;
        forf(k,0,s-1) if(k%i == j && ans[k] == '1') tmp[n] = !tmp[n];
        forf(k,e+1,N-1) if(k%i == j && ans[k] == '1') tmp[n] = !tmp[n];
        int c = 0;

        while(c<n){
            if(tmp[c]) {
                if (mat[c][c]) tmp ^= mat[c];
                else {
                    mat[c] = tmp, cnt++;
                    mat[c][n] = mat[c][n] ^ cyc(i, j);
                    break;
                }
            }
            else c++;
        }
    }

    forf(r,0,n-1) forf(i,0,r-1) if(mat[i][r]) mat[i] ^= mat[r];
    forf(i,s,e) ans[i] = '0'+mat[i-s][n];
}


std::string Solve(int N) {
    ans.resize(N,'-');
    forf(i,1,s) go(i);
    forb(i,N-1,e+1) go2(i);

    solve();
    return ans;
}

• Subtask 1: 100 / 100