Submission #58167

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58167	2018-07-17T05:01:22 Z	노영훈(#1688)	Library (JOI18_library)	C++11	100 / 100	664 ms	592 KB

library

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

int n;

int ask(vector<int> &V){
	// for(int i=0; i<n; i++) cout<<V[i]<<' ';
	// cout<<'\n';
	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;


	// cout<<"FOUND: "<<p+1<<'\n';

	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;
		// cout<<"FOUND: "<<nxt+1<<'\n';
	}

	// for(int i=0; i<n; i++) cout<<ans[i]<<' ';
	// cout<<'\n';

	Answer(ans);
}

Subtask #1

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	248 KB	Output is correct
2	Correct	56 ms	268 KB	Output is correct
3	Correct	53 ms	384 KB	Output is correct
4	Correct	64 ms	400 KB	Output is correct
5	Correct	51 ms	456 KB	Output is correct
6	Correct	35 ms	456 KB	Output is correct
7	Correct	62 ms	488 KB	Output is correct
8	Correct	46 ms	540 KB	Output is correct
9	Correct	46 ms	540 KB	Output is correct
10	Correct	41 ms	540 KB	Output is correct
11	Correct	2 ms	540 KB	Output is correct
12	Correct	3 ms	540 KB	Output is correct
13	Correct	2 ms	540 KB	Output is correct
14	Correct	2 ms	540 KB	Output is correct
15	Correct	4 ms	540 KB	Output is correct
16	Correct	4 ms	540 KB	Output is correct

Subtask #2

81.0 / 81.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	248 KB	Output is correct
2	Correct	56 ms	268 KB	Output is correct
3	Correct	53 ms	384 KB	Output is correct
4	Correct	64 ms	400 KB	Output is correct
5	Correct	51 ms	456 KB	Output is correct
6	Correct	35 ms	456 KB	Output is correct
7	Correct	62 ms	488 KB	Output is correct
8	Correct	46 ms	540 KB	Output is correct
9	Correct	46 ms	540 KB	Output is correct
10	Correct	41 ms	540 KB	Output is correct
11	Correct	2 ms	540 KB	Output is correct
12	Correct	3 ms	540 KB	Output is correct
13	Correct	2 ms	540 KB	Output is correct
14	Correct	2 ms	540 KB	Output is correct
15	Correct	4 ms	540 KB	Output is correct
16	Correct	4 ms	540 KB	Output is correct
17	Correct	664 ms	568 KB	Output is correct
18	Correct	563 ms	576 KB	Output is correct
19	Correct	464 ms	576 KB	Output is correct
20	Correct	454 ms	576 KB	Output is correct
21	Correct	437 ms	576 KB	Output is correct
22	Correct	517 ms	576 KB	Output is correct
23	Correct	458 ms	576 KB	Output is correct
24	Correct	179 ms	576 KB	Output is correct
25	Correct	569 ms	576 KB	Output is correct
26	Correct	476 ms	588 KB	Output is correct
27	Correct	216 ms	588 KB	Output is correct
28	Correct	513 ms	588 KB	Output is correct
29	Correct	494 ms	588 KB	Output is correct
30	Correct	497 ms	592 KB	Output is correct