Submission #1156311

#TimeUsernameProblemLanguageResultExecution timeMemory
1156311dostsLibrary (JOI18_library)C++20
100 / 100
118 ms428 KiB
#include <bits/stdc++.h>
#include "library.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
using namespace std;

void Solve(int N)
{
	
	vector<int> M(N);
	for (int i = 0;i<N;i++) M[i] = 1;
	int edge = -1;
	for (int i = 0;i<N-2;i++) {
		M[i] = 0;
		int x = Query(M);
		if (x == 1) {
			edge = i;
			break;
		}
		M[i] = 1;
	}
	if (edge == -1) edge = N-1;
	vi cover(N,0);
	cover[edge] = 1;
	int covered = 1;
	vi ans{edge+1};
	while (covered < N) {
		vi cand;
		for (int i = 0;i<N;i++) {
			if (!cover[i]) cand.push_back(i);
		}
		int l = 0;
		int r = cand.size()-1;
		while (l<=r) {
			int m = (l+r) >> 1;
			for (int i = 0;i<N;i++) M[i] = 0;
			for (int j = 0;j<=m;j++) M[cand[j]] = 1;
			int x = Query(M);
			for (int i = 0;i<N;i++) if (cover[i]) M[i] = 1;
			int y = Query(M);
			if (x == y) r = m-1;
			else l = m+1;
		}
		covered++;
		cover[cand[l]] = 1;
		ans.push_back(cand[l]+1);
 	}
	Answer(ans);	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...