제출 #1215947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1215947		lighton	Ancient Machine 2 (JOI23_ancient2)	C++20	97 / 100	23 ms	568 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;

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 = 0, e = 999;
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;
        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,'-');
    solve();

    return ans;
}

• Subtask 1: 97 / 100