답안 #823482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
823482	2023-08-12T14:56:18 Z	bachhoangxuan	Ancient Machine 2 (JOI23_ancient2)	C++17	0 / 100	34 ms	420 KB

ancient2

#include "ancient2.h"

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n;
bitset<maxn> bs[maxn],cur;
bool ok[maxn];

bool add(){
    for(int i=n;i>=1;i--){
        if(cur[i]){
            if(!ok[i]){
                bs[i]=cur,ok[i]=true;
                return true;
            }
            else cur^=bs[i];
        }
    }
    return false;
}
void cal_first(int x){
    for(int i=0;i<x;i++){
        cur.reset();
        vector<int> a(i+3),b(i+3);
        for(int j=0;j<i;j++) a[j]=b[j]=j+1;
        a[i]=i+1;b[i]=i+2;
        a[i+1]=b[i+1]=i+1;
        a[i+2]=b[i+2]=i+2;
        int d=Query(i+3,a,b)-i-1;
        cur[i+1]=1;cur[0]=d;
        add();
    }
}
bool check(string s){
    int sz=(int)s.size();
    vector<int> kmp(sz+1,-1);
    vector<int> a(sz+1),b(sz+1);
    for(int i=1;i<=sz;i++){
        int j=kmp[i-1];
        while(j>=0 && s[j]!=s[i-1]) j=kmp[j];
        kmp[i]=j+1;
    }
    vector<vector<int>> nxt(sz+1,vector<int>(2,0));
    for(int i=0;i<=sz;i++){
        int j=kmp[i];
        for(int k=0;k<2;k++){
            if(i<sz && (s[i]-'0')==k) nxt[i][k]=i+1;
            else if(j!=-1) nxt[i][k]=nxt[j][k];
        }
        a[i]=nxt[i][0];b[i]=nxt[i][1];
    }

    if(Query(sz+1,a,b)!=sz) return false;
    else return true;
}
void cal_last(int x){
    string s;
    for(int i=n;i>n-x;i--){
        s='0'+s;
        if(!check(s)) s[0]='1';
        cur.reset();
        cur[i]=1;cur[0]=s[0]-'0';
        add();
    }
}
void cal_mid(int x){
    for(int i=1;i<=51;i++){
        for(int j=0;j<i;j++){
            cur.reset();
            for(int k=0;k<n;k++) if(k%i==j) cur[k+1]=1;
            if(!add()) continue;

            cur.reset();
            for(int k=0;k<n;k++) if(k%i==j) cur[k+1]=1;

            vector<int> a(2*i),b(2*i);
            for(int k=0;k<i;k++){
                if(k!=j){
                    a[k]=b[k]=(k+1)%i;
                    a[i+k]=b[i+k]=i+(k+1)%i;
                }
                else{
                    a[k]=b[i+k]=(k+1)%i;
                    b[k]=a[i+k]=i+(k+1)%i;
                }
            }
            int d=Query(2*i,a,b);

            cur[0]=(d>=i);
            add();x--;
            if(x==0) return;
        }
    }
}
string Solve(int N) {
    n=N;
    cal_first(100);
    cal_last(101);
    cal_mid(799);
    string res;
    for(int i=1;i<=N;i++){
        cur.reset();cur[i]=1;
        for(int j=i;j>=1;j--) if(cur[j]) cur^=bs[j];
        int d=cur[0];
        res+=char('0'+d);
    }
    return res;
}

Subtask #1

0.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	34 ms	420 KB	Wrong Answer [3]
2	Halted	0 ms	0 KB	-