Submission #348240

#	Time	Username	Problem	Language	Result	Execution time	Memory
348240		jamielim	Library (JOI18_library)	C++14	0 / 100	42 ms	384 KiB

library

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

#define pb push_back

int n;
vector<int> ans;
vector<int> rem;
vector<int> test;

void dnc(int s,int e){
	if(s>=e){
		ans.pb(rem[s]);
		return;
	}
	int m=(s+e)/2;
	for(int i=0;i<n;i++)test[i]=0;
	for(int i=s;i<=m;i++)test[rem[i]]=1;
	int cur=Query(test);
	for(int i=0;i<(int)ans.size();i++)test[ans[i]]=1;
	if(cur==Query(test)){ // the answer is in the first half
		dnc(s,m);
	}else{
		dnc(m+1,e);
	}
}

void Solve(int N){
	n=N;
	int endpt=0;
	vector<int> m(n);
	for(int i=0;i<n;i++)m[i]=1;
	for(;endpt<n;endpt++){
		m[endpt]=0;
		if(Query(m)==1)break;
		m[endpt]=1;
	}
	test.resize(n);
	ans.pb(endpt);
	for(int i=0;i<n;i++)if(i!=endpt)rem.push_back(i);
	for(int i=1;i<n;i++){
		dnc(0,n-i-1);
		for(int j=0;j<(int)rem.size()-1;j++){
			if(rem[j]>=ans[i])rem[j]=rem[j+1];
		}
		rem.pop_back();
	}
	for(int i=0;i<n;i++)ans[i]++;
	Answer(ans);
}
/*
5
4
2
5
3
1

9
7
2
1
6
4
8
3
9
5
*/

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