Submission #58186

#	Time	Username	Problem	Language	Result	Execution time	Memory
58186		Diuven	Library (JOI18_library)	C++11	100 / 100	734 ms	600 KiB

library

#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

int n;

int ask(vector<int> &V){
	return Query(V);
}

int find1(int n){
	if(n==1) return 0;
	vector<int> M(n);
	for(int i=0; i<n; i++) M[i]=1;
	for(int i=0; i<n; i++){
		M[i]=0;
		if(ask(M)==1) return i;
		M[i]=1;
	}
	return 0;
}

vector<int> X, Y;
vector<bool> done;

int findnext(int s, int e, vector<int> &V){
	if(s==e) return V[s];
	if(s>e) return 0;
	int m=(s+e)/2;

	for(int i=s; i<=m; i++) X[V[i]]=Y[V[i]]=1;
	int a=ask(X), b=ask(Y);
	for(int i=s; i<=m; i++) X[V[i]]=Y[V[i]]=0;

	if(a==b) return findnext(s, m, V);
	else return findnext(m+1, e, V);
}

void Solve(int N){
	n=N;
	X.resize(n, 0);
	Y.resize(n, 0);
	done.resize(n, false);

	vector<int> ans(n);

	int p=find1(n);
	X[p]=1;
	ans[0]=p+1;
	done[p]=true;

	for(int i=1; i<n; i++){
		vector<int> V;
		for(int i=0; i<n; i++) if(!done[i]) V.push_back(i);
		int nxt=findnext(0, V.size()-1, V);
		ans[i]=nxt+1;
		done[nxt]=true;
		X[nxt]=1;
	}

	Answer(ans);
}

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