Submission #925459

#	Time	Username	Problem	Language	Result	Execution time	Memory
925459		ttamx	Ancient Machine 2 (JOI23_ancient2)	C++17	0 / 100	3027 ms	708 KiB

ancient2

#include "ancient2.h"
#include<bits/stdc++.h>

using namespace std;

string solve_left(int n){
	string ans(n,'0');
	int m=n+2;
	vector<int> a(m),b(m);
	a[n]=b[n]=n;
	a[n+1]=b[n+1]=n+1;
	for(int i=0;i<n;i++){
		a[i]=n;
		b[i]=n+1;
	}
	for(int i=0;i<n;i++){
		int res=Query(m,a,b);
		ans[i]=res-n+'0';
		a[i]=b[i]=i+1;
	}
	return ans;
}

string solve_right(int n){
	string ans(n,'0');
	vector<bool> suf;
	for(int i=1;i<=n;i++){
		suf.insert(suf.begin(),1);
		int m=i+1;
		vector<vector<int>> a(2,vector<int>(m));
		for(int j=0;j<m;j++){
			for(int c=0;c<2;c++){
				int sz=min(j+1,i);
				auto sub1=[&](bool x){
					vector<bool> res(suf.begin()+j-sz+1,suf.begin()+j);
					res.emplace_back(x);
					return res;
				};
				auto sub2=[&](){
					return vector<bool>(suf.begin(),suf.begin()+sz);
				};
				while(sz>0&&sub1(c)!=sub2())sz--;
				a[c][j]=sz;
			}
		}
		int res=Query(m,a[0],a[1])==i;
		ans[n-i]=res+'0';
		suf[0]=res;
	}
	return ans;
}

string Solve(int n) {
	return solve_left(n/2)+solve_right((n+1)/2);
}

• Subtask 1: 0 / 100