Submission #1164630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164630		boclobanchat	Library (JOI18_library)	C++20	100 / 100	143 ms	424 KiB

library

#include"library.h"
#include<bits/stdc++.h>
using namespace std;
void Solve(int N)
{
	vector<int> ans(N);
	vector<bool> ck(N);
	int l=0,r=N-1,pos=0;
	while(l<=r)
	{
		int mid=(l+r)/2;
		vector<int> res(N),resx(N);
		for(int i=0;i<N;i++) resx[i]=true;
		for(int i=l;i<=mid;i++) res[i]=true,resx[i]=false;
		int a=0,b=0;
		for(auto v:res) if(v)
		{
			a=Query(res);
			break;
		}
		for(auto v:resx) if(v)
		{
			b=Query(resx);
			break;
		}
		if(a+1==b) l=mid+1;
		else r=mid-1,pos=mid;
	}
	ans[0]=pos+1,ck[pos]=true;
	int pre=pos,lt=1,rt=N-1;
	for(int i=1;i<N;i++)
	{
		int l=0,r=N-2;
		pos=N-1;
		while(l<=r)
		{
			int mid=(l+r)/2;
			vector<int> res(N),resx(N);
			for(int i=0;i<N;i++) resx[i]=!ck[i];
			for(int i=0;i<=mid;i++) res[i]^=(!ck[i]),resx[i]^=(!ck[i]);
			res[pre]=true,resx[pre]=false;
			int a=0,b=0;
			for(auto v:res) if(v)
			{
				a=Query(res);
				break;
			}
			for(auto v:resx) if(v)
			{
				b=Query(resx);
				break;
			}
			if(a!=b+1) l=mid+1;
			else r=mid-1,pos=mid;
		}
		if(i&1) ans[rt--]=pos+1;
		else ans[lt++]=pos+1;
		pre=pos,ck[pos]=true;
	}
	Answer(ans);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81