제출 #376446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376446		peijar	도서관 (JOI18_library)	C++17	100 / 100	372 ms	492 KiB

library

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

void Solve(int nbElem)
{
	vector<int> ret(nbElem);
	if (nbElem == 1)
	{
		ret[0] = 1;
		Answer(ret);
		return ;
	}
	vector<int> tabRequete(nbElem,1);
	int extremGauche=-1;
	for (int i(0); i < nbElem; ++i)
	{
		tabRequete[i] = 0;
		int query = Query(tabRequete);
		tabRequete[i] = 1;
		if (query == 1)
		{
			extremGauche = i;
			break;
		}
	}
	fill(tabRequete.begin(), tabRequete.end(), 0);
	tabRequete[extremGauche] = 1;
	vector<int> restant;
	for (int i(0); i < nbElem; ++i)
		if (i != extremGauche)
			restant.push_back(i);

	ret[0] = extremGauche;
	for (int i(1); i < nbElem; ++i)
	{
		int deb(0), fin((int)restant.size()-1);
		while (deb < fin)
		{
			int mid = (deb + fin) / 2;
			tabRequete.assign(nbElem, 0);
			for (int iReq(deb); iReq <= mid; ++iReq)
				tabRequete[restant[iReq]] = 1;
			int retSans = Query(tabRequete);
			tabRequete[ret[i-1]] = 1;
			int retAvec = Query(tabRequete);
			if (retAvec == retSans)
				fin = mid;
			else
				deb = mid+1;
		}
		ret[i] = restant[deb];
		restant.erase(lower_bound(restant.begin(), restant.end(), restant[deb]));
	}
	for (auto &v : ret) v++;
	Answer(ret);
}

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