Submission #1161596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161596		LCJLY	Library (JOI18_library)	C++20	100 / 100	149 ms	432 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;
 
//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

//Answer()
//Query()

void Solve(int n){
	vector<int>lft;
	vector<int>rgt;
	
	if(n==1){
		Answer({1});
		return;
	}
	
	//find an element
	int l=1;
	int r=n-1;
	int best=r;
	int mid;
	while(l<=r){
		mid=(l+r)/2;
		vector<int>v(n,0);
		for(int y=1;y<=mid;y++){
			v[y]=1;
		}
		int a=Query(v);
		v[0]=1;
		int b=Query(v);
		if(a!=b-1){
			best=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	lft.push_back(best);
	rgt.push_back(0);
	
	for(int x=0;x<n;x++){
		int l=0;
		int r=n-1;
		int best=n;
		int mid;
		
		while(l<=r){
			mid=(l+r)/2;
			vector<int>v(n,0);
			for(int y=0;y<=mid;y++){
				v[y]=1;
			}	
			
			vector<int>v2=v;
			for(auto it:rgt){
				v[it]=0;
				v2[it]=0;
			}
			for(auto it:lft){
				v[it]=0;
				v2[it]=1;
			}
			int a,b;
			bool amos=false;
			bool amos2=false;
			for(auto it:v) amos|=it;
			for(auto it:v2) amos2|=it;
			if(amos) a=Query(v);
			else a=0;
			if(amos2) b=Query(v2);
			else b=0;
			if(amos&&a==b){
				best=mid;
				r=mid-1;
			}
			else l=mid+1;
		}
		if(best==n) break;
		lft.push_back(best);
	}	
	
	for(int x=0;x<n;x++){
		int l=0;
		int r=n-1;
		int best=n;
		int mid;
		
		while(l<=r){
			mid=(l+r)/2;
			vector<int>v(n,0);
			for(int y=0;y<=mid;y++){
				v[y]=1;
			}	
			
			vector<int>v2=v;
			for(auto it:lft){
				v[it]=0;
				v2[it]=0;
			}
			for(auto it:rgt){
				v[it]=0;
				v2[it]=1;
			}
			
			int a,b;
			bool amos=false;
			bool amos2=false;
			for(auto it:v) amos|=it;
			for(auto it:v2) amos2|=it;
			if(amos) a=Query(v);
			else a=0;
			if(amos2) b=Query(v2);
			else b=0;
			
			if(amos&&a==b){
				best=mid;
				r=mid-1;
			}
			else l=mid+1;
		}
		
		if(best==n) break;
		rgt.push_back(best);
	}
	//show4(lft,lft);
	reverse(lft.begin(),lft.end());
	for(auto it:rgt) lft.push_back(it);
	for(auto &it:lft) it++;
	//show4(lft,lft);
	Answer(lft);
}

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