oj.uz

Submission #1079964

# Submission time Handle Problem Language Result Execution time Memory
1079964 2024-08-29T05:06:51 Z daoquanglinh2007 Library (JOI18_library) C++17
0 / 100
 24 ms 344 KB 
#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]) break;
		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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 344 KB # of queries: 2367
2 Incorrect 22 ms 344 KB Wrong Answer [8]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 344 KB # of queries: 2367
2 Incorrect 22 ms 344 KB Wrong Answer [8]
3 Halted 0 ms 0 KB -