제출 #899247

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899247		jamjanek	Ancient Machine 2 (JOI23_ancient2)	C++17	100 / 100	38 ms	1900 KiB

ancient2

#include "ancient2.h"
#include<bits/stdc++.h>
using namespace std;
const int prefixL = 100, sufixL = 101; 
const int R = 1001;
bool prefix(int k){
	int m = k+1+2;
	vector<int>a(m), b(m);
	for(int i=0;i<k;i++){
		a[i] = i+1;
		b[i] = i+1;
	}
	a[k] = k+1;
	b[k] = k+2;
	a[k+2] = k+2;
	b[k+2] = k+2;
	a[k+1] = k+1;
	b[k+1] = k+1;
	return Query(m,a,b)==(k+2);
}

string PoznajSufix(int k){
	string s="2";
	while((int)s.size()-1<k){
		s[0]='0';
		s = '2' + s;
		int m = s.size();
		vector<int>a(m), b(m);
		vector<int>kmp(m);
		kmp[0] = 0;
		kmp[1] = 0;
		for(int i=2;i<m;i++){
			int j = kmp[i-1];
			while(j!=0 && s[j+1]!=s[i])
				j = kmp[j];
			if(s[j+1]==s[i])
				j++;
			kmp[i] = j;
		}
		for(int i=0;i<m-1;i++){
			if(s[i+1]=='0'){
				a[i] = i+1;
				int j = kmp[i];
				while(s[j+1]!='1' && j!=0)j = kmp[j];
				if(s[j+1]=='1')j++;
				b[i] = j;
			}
			else if(s[i+1]=='1'){
				int j = kmp[i];
				while(s[j+1]!='0' && j!=0)j = kmp[j];
				if(s[j+1]=='0')j++;
				a[i] = j;
				b[i] = i+1;
			}
		}
		int j = kmp[m-1];
		while(s[j+1]!='0' && j!=0)j = kmp[j];
		if(s[j+1]=='0')j++;
		a[m-1] = j;

		j = kmp[m-1];
		while(s[j+1]!='1' && j!=0)j = kmp[j];
		if(s[j+1]=='1')j++;
		b[m-1] = j;
		if(Query(m, a, b)!=m-1)
			s[1] = '1';
	}
	reverse(s.begin(), s.end());s.pop_back();reverse(s.begin(), s.end());
	return s;
}

bool parity(int mod, int r){
	int m = 2*mod;
	vector<int>a(m),b(m);
	for(int i=0;i<mod;i++){
		if(i==r){
			a[i] = (i+1)%mod;
			b[i] = mod+(i+1)%mod;
		}
		else{
			a[i] = (i+1)%mod;
			b[i] = (i+1)%mod;
		}
	}
	for(int i=0;i<mod;i++){
		if(i==r){
			a[i+mod] = mod+(i+1)%mod;
			b[i+mod] = (i+1)%mod;
		}
		else{
			a[i+mod] = mod+(i+1)%mod;
			b[i+mod] = mod+(i+1)%mod;
		}
	}
	return Query(m, a, b)>=mod;
}

bitset<R>gauss[R-1];
int przekotna = 0;
void dodaj(bitset<R>X){
	for(int i=0;i<R-1;i++){
		if(X[i]){
			if(gauss[i][i]==0){
				gauss[i] = X;
				przekotna++;
				break;
			}
			X^=gauss[i];
		}
	}
}
bool LiniowoNiezalezne(bitset<R>X){
	for(int i=0;i<R-1;i++){
		if(X[i]){
			if(gauss[i][i]==0)return 1;
			X^=gauss[i];
		}
	}
	return 0;
}

bool odczytaj(bitset<R>X){
	for(int i=0;i<R-1;i++){
		if(X[i]){
			X^=gauss[i];
		}
	}
	return X[R-1];	
}

string Solve(int N) {
	
	string s;
	for(int i=0;i<prefixL;i++){
		bitset<R>pom;
		pom[R-1] = prefix(i);
		pom[i] = 1;
		dodaj(pom);
		//printf("%d\n", (int)pom[R-1]);
//		s.push_back('0'+prefix(s.size()));
	}
	string sufix;
	sufix = PoznajSufix(sufixL);
	for(int i=N-1;i>= N-sufixL;i--){
		bitset<R>pom;
		pom[i] = 1;
		pom[R-1] = (sufix[i-N+sufixL]-'0');
		dodaj(pom);
		//printf(" %d\n", (int)pom[R-1]);
	}
	for(int mod=1;;mod++){
		for(int reszta=0;reszta<mod;reszta++){
			bitset<R>pom;
			for(int i=0;i<R-1;i++)
				if(i%mod==reszta)
					pom[i] = 1;
			if(LiniowoNiezalezne(pom)){
				pom[R-1] = parity(mod, reszta);
				//printf("%d\n", parity(mod, reszta));
				dodaj(pom);
				//printf("%d %d   %d\n", mod, reszta, przekotna);
				//cout<<pom<<"\n";
			}
			if(przekotna==R-1)break;
		}
		if(przekotna==R-1)break;
	}
	for(int i=0;i<R-1;i++){
		bitset<R>pom;
		pom[i] = 1;
		s+='0'+odczytaj(pom);
	}
	//cout<<s<<"\n";
	return s;
}

• Subtask 1: 100 / 100