Submission #812146

#	Time	Username	Problem	Language	Result	Execution time	Memory
812146		jangwonyoung	Ancient Machine 2 (JOI23_ancient2)	C++17	100 / 100	20 ms	336 KiB

ancient2

#include "ancient2.h"

#include <string>
#include <vector>

namespace {

int variable_example = 1;

}  // namespace

#include<bits/stdc++.h>
using namespace std;
int n;
string ans;

int si[1000],sj[1000],sk[1000];
bool check(int i,int j,char c){
	ans[i]=c;
	for(int k=i-j; k>=j-1 ;k-=j){
		bool same=true;
		for(int l=0; l<j ;l++){
			if(ans[k-l]!=ans[i-l]){
				same=false;break;
			}
		}
		if(same) return false;
	}
	return true;
}
int build(int i,int j,int cl){
	int m=2*j+1+cl;
	vector<int>a(m),b(m);
	for(int k=0; k<j ;k++){
		a[k]=a[k+j]=b[k]=b[k+j]=k%j+1;
		if(ans[i-j+1+k]=='0') a[k+j]+=j;
		else b[k+j]+=j;
	}
	int iu=2*j+1;
	a[2*j]=iu;
	b[2*j]=iu+(1000-i)%cl;
	for(int k=0; k<cl ;k++){
		a[iu+k]=b[iu+k]=iu+(k+1)%cl;
	}
	int st=j-i%j-1;
	if(st==0) st=j;
	for(auto &c:a) if(c==0 || c==st) c^=st;
	for(auto &c:b) if(c==0 || c==st) c^=st;
	swap(a[0],a[st]);
	swap(b[0],b[st]);
	int res=Query(m,a,b);
	return res;
}
void boom(int i,int j){
	//cout << "BOOM " << i << ' ' << j << ' ' << ans[i] << endl;
	int cl=1;
	while(cl*(cl+1)<(1000-i)*2) cl++;
	int res=build(i,j,cl);
	if(res<2*j){//string not found
		ans[i]^=1;
		return;
	}
	if(i==n-1) return;
	if(res==2*j){
		ans[n-1]=ans[i];
		ans[i]^=1;
		return;
	}
	int res2=build(i,j,cl+1);
	int r1=res-2*j-1,r2=res2-2*j-1;
	int z=0;
	//if(res2==52) exit(0);
	while(z%cl!=r1 || z%(cl+1)!=r2) z++;
	int pos=n-z%(1000-i)-2;
	sj[i]=j;sk[i]=pos;
	ans[pos]=ans[i];
	ans[pos+1]='0'+(z>=(1000-i));
	if(pos!=i) ans[i]^=1;
}
string Solve(int N){
	n=N;
	ans.resize(N);
	for(int i=0; i<N ;i++) ans[i]='2';
	for(int i=0; i<N ;i++){
		//cout << "solve " << i << endl;
		if(ans[i]!='2') continue;
		{
			for(int x=0; x<i ;x++){
				if(sj[x]==0 || (i-x)%sj[x]!=0 || i>=sk[x]) continue;
				bool same=true;
				for(int j=1; j<sj[x] ;j++){
					if(ans[i-j]!=ans[x-j]){
						same=false;
						break;
					}
				}
				if(same){
					ans[i]=ans[x];
					break;
				}
			}
		}
		if(ans[i]!='2') continue;
		for(int j=1; ;j++){
			bool done=false;
			if(check(i,j,'0')){
				done=true;
				boom(i,j);
			}
			else if(check(i,j,'1')){
				done=true;
				boom(i,j);
			}
			if(done) break;
		}
		//cout << "progress " << i << endl;
		/*for(int i=0; i<n ;i++) cout << ans[i];
		cout << endl;*/
	}
	return ans;
}

Compilation message (stderr)

ancient2.cpp:8:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    8 | int variable_example = 1;
      |     ^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100