Submission #529115

#	Time	Username	Problem	Language	Result	Execution time	Memory
529115		ftkbrian	Library (JOI18_library)	C++14	100 / 100	455 ms	412 KiB

library

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

vector<int> now,lef;
int chk[1010];
void Solve(int N)
{
	if(N == 1) {
		now.push_back(1);
		Answer(now);
		return;
	}
	vector<int> Qur(N,0);
	for(int i = 0 ; i < N ; i++) {
		for(int q = 0 ; q < N ; q++)
			if(q == i) Qur[q] = 0;
			else Qur[q] = 1;
		if(Query(Qur) == 1) {
			now.push_back(i);
			break;
		}
	}
	for(int i = 0 ; i < N ; i++) Qur[i] = 0;
	Qur[now[0]] = 1;
	for(int i = 0 ; i < N ; i++) {
		if(i == now[0]) continue;
		Qur[i] = 1;
		if(Query(Qur) == 1) {
			now.push_back(i); break;
		}
		Qur[i] = 0;
	}
	for(auto i : now) chk[i] = 1;
	for(int i = 0 ; i < N ; i++)
		if(!chk[i]) lef.push_back(i);
	///현재 now에 들어있는 놈이 왼쪽 끝이라 하고 문제를 해결할 것
	for(int i = 2 ; i < N ; i++) {
		int lo = 0,hi = lef.size()-1,loc;
		while(lo <= hi) {
			int mi = lo+hi>>1;
			for(int q = 0 ; q < N ; q++) Qur[q] = 0;
			for(auto q : now) Qur[q] = 1;
			for(int q = lo ; q <= mi ; q++) Qur[lef[q]] = 1;
			int tar = Query(Qur);
			Qur[now.back()] = 0;
			int tar2 = Query(Qur);
			if(tar != tar2) hi = mi-1,loc = mi;
			else lo = mi+1;
		}
		now.push_back(lef[loc]);
		swap(lef[loc],lef.back());
		lef.pop_back();
	}
	for(auto& i : now) i++;
	Answer(now);
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |    int mi = lo+hi>>1;
      |             ~~^~~
library.cpp:51:24: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |   now.push_back(lef[loc]);
      |                        ^

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