Submission #62597

#	Time	Username	Problem	Language	Result	Execution time	Memory
62597		gusfring	Library (JOI18_library)	C++14	100 / 100	696 ms	596 KiB

library

#include <bits/stdc++.h>
#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