Submission #537436

#	Time	Username	Problem	Language	Result	Execution time	Memory
537436		chaoyue	Library (JOI18_library)	C++14	100 / 100	465 ms	208 KiB

library

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

int n;
vector<int> v;

int findedge(){
	int m, l=0, r=(int)v.size()-1;
	vector<int> ma(n, 0), mb(n, 0); //ma is query array for a, mb is query array for b
	for(int i=0; i<(int)v.size(); i++){
		ma[v[i]] = 1;
	}
	while(r > l){
		//cut a in half and get result
		m = (l + r) / 2;  //2nd half of a will be discarded, 1st half (including split) will be included
		for(int i=m+1; i<=r; i++){
			ma[v[i]] = 0;
			mb[v[i]] = 1;
		}
		if(Query(ma) >= Query(mb)){  //take remain
			r = m;
		}
		else{  //take discarded
			for(int i=m+1; i<=r; i++){
				ma[v[i]] = 1;
				mb[v[i]] = 0;
			}
			for(int i=l; i<=m; i++){
				ma[v[i]] = 0;
				mb[v[i]] = 1;
			}
			l = m+1;
		}
	}
	return v[l];
}

void Solve(int N){
	n = N;
	int tmp, l=0, r=n-1;
	vector<int> ans(n), m(n, 0);
	v.resize(n);
	for(int i=0; i<n; i++){
		v[i] = i;
	}
	for(int i=0; i<n; i++){
		tmp = findedge();
		//cout<<"tmp: "<<tmp<<endl;
		v.erase(find(v.begin(), v.end(), tmp));
		if(!l){
			ans[l] = tmp;
			l++;
		}
		else{
			//Query l and tmp
			m[ans[l-1]] = 1;
			m[tmp] = 1;
			if(Query(m) == 1){
				m[ans[l-1]] = 0;
				ans[l] = tmp;
				l++;
			}
			else{
				m[ans[l-1]] = 0;
				ans[r] = tmp;
				r--;
			}
			m[tmp] = 0;
		}
	}
	for(int i=0; i<n; i++){
		ans[i]++;
	}
	Answer(ans);
}

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