Submission #1211657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211657		jellybean	Library (JOI18_library)	C++20	100 / 100	151 ms	512 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;
#define pb push_back

vector<int>v;
vector<int>help;
int n;
int query(int l, int r, int x){ //queries for the thing adjacent to x
	int sz = r-l+1;
	if(sz == 1){
		return help[l];
	}
	int m = (l+r)/2;
	vector<int>v1;
	for(int i=0; i<n; i++) v1.pb(0);
	for(int i=l; i<=m; i++){
		//cout<<1<<" "<<help[i]-1<<endl;
		v1[help[i]-1] = 1;
	}
	//for(auto i: v1) cout<<i<<" ";
	//cout<<endl;
	int res = Query(v1);
	v1[x-1] = 1;
	int res1 = Query(v1);
	if(res1 <= res){
		return query(l,m,x);
	} else {
		return query(m+1,r,x);
	}
}

void Solve(int N){
	
	n = N;
	for(int i=0; i<n; i++) v.pb(0);
	
	set<int>s;
	for(int i=1; i<=n; i++) s.insert(i);
	
	deque<int>d;
	d.pb(1);
	
	bool f=0;
	while(1){
		//cout<<d.back() <<endl;
		s.erase(d.back());
		if(s.empty()) break;
		for(int i=0; i<n; i++) v[i] = 0;
		for(auto i: s) v[i-1] = 1;
		int res = Query(v);
		//for(auto i: v) cout<<i<<" ";
		//cout<<endl;
		v[d.back()-1] = 1;
		int res1 = Query(v);
		if(res1 > res){ //go to the other end
			f = 1;
			break;
		} else {
			//cout<<1<<endl;
			help.clear();
			v[d.back()-1] = 0;
			for(int i=0; i<n; i++) if(v[i]) help.pb(i+1);
			d.pb(query(0,help.size()-1,d.back()));
		}
	}
	
	if(!f){
		vector<int>ans;
		for(auto i: d) ans.pb(i);
		Answer(ans);
		return;
	}
	
	s.insert(1);
	while(1){
		s.erase(d.front());
		if(s.empty()) break;
		for(int i=0; i<n; i++) v[i] = 0;
		for(auto i: s) v[i-1] = 1;
		help.clear();
		for(int i=0; i<n; i++) if(v[i]) help.pb(i+1);
		d.push_front(query(0,help.size()-1,d.front()));
	}
	
	vector<int>ans;
	for(auto i: d) ans.pb(i);
	Answer(ans);
}

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