답안 #58164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58164	2018-07-17T04:47:19 Z	노영훈(#1688)	도서관 (JOI18_library)	C++11	0 / 100	62 ms	716 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){
	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 -1;
}

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

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

	vector<int> Y(n);
	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]]=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);
	done.resize(n);

	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> Y;
		for(int i=0; i<n; i++) if(!done[i]) Y.push_back(i);
		int nxt=findnext(0, Y.size()-1, Y);
		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

0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	248 KB	Output is correct
2	Correct	54 ms	308 KB	Output is correct
3	Correct	61 ms	392 KB	Output is correct
4	Correct	52 ms	468 KB	Output is correct
5	Correct	41 ms	488 KB	Output is correct
6	Correct	30 ms	536 KB	Output is correct
7	Correct	30 ms	540 KB	Output is correct
8	Correct	62 ms	540 KB	Output is correct
9	Correct	52 ms	540 KB	Output is correct
10	Correct	34 ms	544 KB	Output is correct
11	Runtime error	2 ms	716 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Halted	0 ms	0 KB	-

Subtask #2

0 / 81.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	248 KB	Output is correct
2	Correct	54 ms	308 KB	Output is correct
3	Correct	61 ms	392 KB	Output is correct
4	Correct	52 ms	468 KB	Output is correct
5	Correct	41 ms	488 KB	Output is correct
6	Correct	30 ms	536 KB	Output is correct
7	Correct	30 ms	540 KB	Output is correct
8	Correct	62 ms	540 KB	Output is correct
9	Correct	52 ms	540 KB	Output is correct
10	Correct	34 ms	544 KB	Output is correct
11	Runtime error	2 ms	716 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Halted	0 ms	0 KB	-