oj.uz

Submission #994953

# Submission time Handle Problem Language Result Execution time Memory
994953 2024-06-08T08:49:36 Z NintsiChkhaidze Library (JOI18_library) C++17
100 / 100
 212 ms 452 KB 
#include "library.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
using namespace std;

 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll B) {
	return (ull)rng() % B;
}
 
int n;
 
void Solve(int N){
	n = N;
	
	vector<int> ans(N),fix(N),del(N);
	for(int i = 0; i < N; i++) {
		ans[i] = fix[i] = 0;
	}
	
	int cnt = 0,tot = N;
	while (tot > 0){
		int k;
		while (1){
			k = rnd(N);
			if (del[k]) continue;
			break;
		}	
		
		tot -= 1;
		del[k] = 1;
	
		vector <int> M(N);
		for (int i=0;i<N;i++)
			M[i] = 1;
		M[k] = 0;
		
		int A = 1;
		if (N > 1) A = Query(M);
		if (A == 1) {
			fix[k] = 1;
			ans[0] = k;
			break;
		}
	}
	
	for (int i = 0; i + 1 < N; i++){
 	
 		vector <int> vec;
 		for (int j = 0; j < N; j++){
 			if (fix[j]) continue;
 			vec.pb(j);
		}
		
		int l = 0, r = vec.size() - 1;
		int res=0;
		for (int j = 0; j < 10; j++){
			if (l > r) break;
			vector <int> M(N);
			
			int mid = (l + r)/2;
			for (int w=0;w<N;w++)
				M[w]=0;
			for (int w = l; w <= mid; w++)	
				M[vec[w]] = 1;
				
			M[ans[i]] = 1;
			int A = Query(M);
			
			M[ans[i]] =0 ;
			int B = Query(M);
			if (A == B){
				res = mid;
				r = mid - 1;
			}else{
				l = mid + 1;
			}
		}
		
		int find = vec[res];
		fix[find] = 1;
		ans[i + 1] = find;
	}
	
	for (int i=0;i<N;i++)
		ans[i] += 1;
	Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:24:6: warning: unused variable 'cnt' [-Wunused-variable]
   24 |  int cnt = 0,tot = N;
      |      ^~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 344 KB # of queries: 2405
2 Correct 33 ms 344 KB # of queries: 2447
3 Correct 29 ms 344 KB # of queries: 2556
4 Correct 19 ms 344 KB # of queries: 2546
5 Correct 29 ms 344 KB # of queries: 2529
6 Correct 24 ms 344 KB # of queries: 2576
7 Correct 29 ms 344 KB # of queries: 2634
8 Correct 26 ms 344 KB # of queries: 2406
9 Correct 26 ms 344 KB # of queries: 2538
10 Correct 11 ms 344 KB # of queries: 1513
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 3
13 Correct 0 ms 344 KB # of queries: 5
14 Correct 0 ms 344 KB # of queries: 9
15 Correct 2 ms 344 KB # of queries: 85
16 Correct 2 ms 344 KB # of queries: 194

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 344 KB # of queries: 2405
2 Correct 33 ms 344 KB # of queries: 2447
3 Correct 29 ms 344 KB # of queries: 2556
4 Correct 19 ms 344 KB # of queries: 2546
5 Correct 29 ms 344 KB # of queries: 2529
6 Correct 24 ms 344 KB # of queries: 2576
7 Correct 29 ms 344 KB # of queries: 2634
8 Correct 26 ms 344 KB # of queries: 2406
9 Correct 26 ms 344 KB # of queries: 2538
10 Correct 11 ms 344 KB # of queries: 1513
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 3
13 Correct 0 ms 344 KB # of queries: 5
14 Correct 0 ms 344 KB # of queries: 9
15 Correct 2 ms 344 KB # of queries: 85
16 Correct 2 ms 344 KB # of queries: 194
17 Correct 202 ms 344 KB # of queries: 17439
18 Correct 206 ms 344 KB # of queries: 17032
19 Correct 172 ms 344 KB # of queries: 17231
20 Correct 188 ms 344 KB # of queries: 16289
21 Correct 166 ms 344 KB # of queries: 15121
22 Correct 199 ms 344 KB # of queries: 17573
23 Correct 204 ms 344 KB # of queries: 17632
24 Correct 69 ms 344 KB # of queries: 8109
25 Correct 198 ms 452 KB # of queries: 16851
26 Correct 208 ms 344 KB # of queries: 16251
27 Correct 85 ms 344 KB # of queries: 7947
28 Correct 212 ms 344 KB # of queries: 18562
29 Correct 183 ms 344 KB # of queries: 16156
30 Correct 201 ms 344 KB # of queries: 16192