Submission #1166209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166209		crackhead	Library (JOI18_library)	C++20	100 / 100	116 ms	432 KiB

library

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

std::vector <int> arr;

bool can(int mid, int node, int N){
	std::vector <int> temp(N, 0);
	for(int i=0; i<=mid; i++){
		temp[arr[i]]=1;
	}
	int without=Query(temp);
	temp[node]=1;
	if(Query(temp)==without+1) return true;
	else return false;
}

void Solve(int N)
{
	vector<int> M(N);
	std::vector <int> qry(N, 1), res;
	for(int i=0; i<N; i++) arr.push_back(i);//all is 0 indexed
	if(N==1) {
		Answer({1});
		return;
	}
	//find one leaf of the line
	int node;//u gonna find the adj of this node 
	for(int i=0; i<N; i++){
		qry[arr[i]]=0;
		if(Query(qry)==1){
			node=i;
			break;
		}
		qry[arr[i]]=1;
	}
	for(int i=0; i<N; i++){
		//bsta on each one to find adj
		res.push_back(node+1);
		auto it=find(arr.begin(), arr.end(), node);
		arr.erase(it);
		
		int lo=-1, hi=arr.size();
		while(lo+1<hi){
			int mid=(lo+hi)/2;
			if(can(mid, node, N)) lo=mid;
			else hi=mid;
		}
		//hi is adj?
		node=arr[hi];
	}
	

	Answer(res);
}

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