Submission #1079971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079971		vjudge1	Library (JOI18_library)	C++17	100 / 100	225 ms	344 KiB

library

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

#define isz(a) (int)(a).size()

void Solve(int N){
	if (N == 1){
		Answer({1});
		return;
	}
	if (N == 2){
		Answer({1, 2});
		return;
	}
	vector <int> p(N);
	for (int i = 0; i < N; i++){
		vector <int> arr = {};
		for (int j = 0; j < N; j++)
			if (j == i) arr.push_back(0); else arr.push_back(1);
		if (Query(arr) == 1){
			p[0] = i;
			break;
		}
	}
	for (int i = 0; i < N; i++){
		if (i == p[0]) continue;
		vector <int> arr = {};
		for (int j = 0; j < N; j++)
			if (j == p[0] || j == i) arr.push_back(1); else arr.push_back(0);
		if (Query(arr) == 1){
			p[1] = i;
			break;
		}
	}
	bool mark[N];
	memset(mark, 0, sizeof(mark));
	mark[p[0]] = mark[p[1]] = 1;
	for (int i = 2; i < N; i++){
		vector <int> rem = {};
		for (int j = 0; j < N; j++)
			if (!mark[j]) rem.push_back(j);
		int l = 0, r = isz(rem)-2, res = isz(rem)-1;
		while (l <= r){
			int mid = (l+r)/2;
			vector <int> arr(N, 0);
			for (int j = 0; j < i; j++) arr[p[j]] = 1;
			for (int j = 0; j <= mid; j++) arr[rem[j]] = 1;
			int x = Query(arr), y;
			arr[p[i-1]] = 0;
			y = Query(arr);
			if (x < y){
				res = mid;
				r = mid-1;
			}
			else l = mid+1;
		}
		p[i] = rem[res];
		mark[p[i]] = 1;
	}
	for (int i = 0; i < N; i++) p[i]++;
	Answer(p);
}

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