Submission #936024

#	Time	Username	Problem	Language	Result	Execution time	Memory
936024		yhkhoo	Library (JOI18_library)	C++17	100 / 100	197 ms	448 KiB

library

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

void Solve(int N){
	if(N == 1){
		Answer({1});
		return;
	}
	vector<int> res(N);
	vector<int> m0(N, 1);
	int le=-1, re=-1;
	for(int i=0; i<N; i++){
		if(i != 0){
			m0[i-1] = 1;
		}
		m0[i] = 0;
		if(Query(m0) == 1){
			if(le == -1){
				le = i;
			}
			else{
				re = i;
			}
		}
	}
	vector<int> cons(N);
	for(int i=0; i<N; i++){
		cons[i] = i;
	}
	cons.erase(lower_bound(cons.begin(), cons.end(), le));
	cons.erase(lower_bound(cons.begin(), cons.end(), re));
	res[0] = le;
	res[N-1] = re;
	for(int i=1; i<N-1; i++){
		int l = 0, r = cons.size()-1, m;
		while(l < r){
			m = (l+r)/2;
			vector<int> m1(N, 0);
			for(int i=l; i<=m; i++){
				m1[cons[i]] = 1;
			}
			m1[res[i-1]] = 1;
			auto wit = Query(m1);
			m1[res[i-1]] = 0;
			auto wito = Query(m1);
			if(wito == wit){ // is in
				r = m;
			}
			else{ // not in
				l = m+1;
			}
		}
		res[i] = cons[l];
		cons.erase(cons.begin()+l);
	}
	for(int i=0; i<N; i++){
		res[i]++;
	}
	Answer(res);
}

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