Submission #654373

#	Time	Username	Problem	Language	Result	Execution time	Memory
654373		socpite	Library (JOI18_library)	C++17	100 / 100	316 ms	328 KiB

library

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,sse4.2")
#include "library.h"
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;
typedef long double ld;
typedef pair<int, pair<int, int>> ftype;

const int inf = 1e9;
const int maxn = 1e3+5;

int n, ch;

vector<int> qvec;
int mm[maxn];
void Solve(int N){
    n = N;
	if(n == 1){
		Answer({1});
		return;
	}
    vector<int> re;
	vector<int> crr;
	for(int i = 1; i <= n ; i++){
		qvec.assign(n, 1);
		qvec[i-1]=0;
		if(Query(qvec) == 1){
			ch = i;
			mm[i]=1;
			break;
		}
	}
	for(int i = 0; i < n-1; i++){
		crr.clear();
		for(int j = 1; j <= n; j++)if(!mm[j])crr.push_back(j);
		int l = 0, r = crr.size()-1;
		while(l < r){
			int mid = (l+r)>>1;
			qvec.assign(n, 0);
			for(int i = l; i <= mid; i++)qvec[crr[i]-1]=1;
			qvec[ch-1]=1;
			int lt = Query(qvec);
			for(auto v: crr)qvec[v-1]^=1;
			qvec[ch-1]=0;
			int rt = Query(qvec);
			if(lt > rt)r = mid;
			else l = mid+1;
		}
		mm[crr[l]]=1;
		re.push_back(crr[l]);
	}
	re.push_back(ch);
	Answer(re);

}

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