oj.uz

Submission #994907

# Submission time Handle Problem Language Result Execution time Memory
994907 2024-06-08T08:23:44 Z NintsiChkhaidze Library (JOI18_library) C++17
0 / 100
 38 ms 344 KB 
#include "library.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
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),mm(N);
	for(int i = 0; i < N; i++) {
		ans[i] = fix[i] = 0;
		del[i] = 0;
		mm[i] = 1;
	}
	
	int cnt = 0,tot = N;
	while (tot > 0){
		int k;
		while (1){
			k = rnd(N);
			if (del[k]) continue;
			break;
		}
		
		del[k] = 1;
		tot -= 1;
		mm[k] = 0;
		if (Query(mm) == 1){
			++cnt;
			if (cnt == 1) ans[0] = k;
			else ans[N - 1] = k; 
			fix[k] = 1;
		}
		
		if (cnt == 2) break;
		mm[k] = 1;
	}
	
	for (int i = 0; i + 2 < N; i++){

		int find = 0;
		for (int j = 0; j < 10; j++){
			vector <int> M(N);
			int ones=0;
			for (int w = 0; w < N; w++){
				M[w] = 0;
				if (fix[w]) M[w] = 0;
				else {
					int bt = ((w >> j) & 1);
					if (bt) M[w] = 1,++ones;
				}
			}
			
			M[ans[i]] = 1;
			ones++;
			if (ones == 1) continue;
			
			int A = Query(M);
			
			M[ans[i]] = 0;
			ones--;
			int B = Query(M);
			if (A == B) find |= (1<<j);
		}
		
		fix[find] = 1;
		ans[i + 1] = find;
	}
	
	for (int i=0;i<N;i++)
		ans[i] += 1;
	Answer(ans);
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 344 KB # of queries: 3127
2 Correct 22 ms 344 KB # of queries: 3137
3 Correct 20 ms 344 KB # of queries: 3251
4 Correct 27 ms 344 KB # of queries: 3272
5 Correct 38 ms 344 KB # of queries: 3316
6 Correct 22 ms 344 KB # of queries: 3249
7 Correct 36 ms 344 KB # of queries: 3244
8 Correct 27 ms 344 KB # of queries: 3203
9 Correct 33 ms 344 KB # of queries: 3292
10 Correct 12 ms 344 KB # of queries: 1884
11 Runtime error 0 ms 344 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 344 KB # of queries: 3127
2 Correct 22 ms 344 KB # of queries: 3137
3 Correct 20 ms 344 KB # of queries: 3251
4 Correct 27 ms 344 KB # of queries: 3272
5 Correct 38 ms 344 KB # of queries: 3316
6 Correct 22 ms 344 KB # of queries: 3249
7 Correct 36 ms 344 KB # of queries: 3244
8 Correct 27 ms 344 KB # of queries: 3203
9 Correct 33 ms 344 KB # of queries: 3292
10 Correct 12 ms 344 KB # of queries: 1884
11 Runtime error 0 ms 344 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -