oj.uz

Submission #994870

# Submission time Handle Problem Language Result Execution time Memory
994870 2024-06-08T07:56:31 Z NintsiChkhaidze Library (JOI18_library) C++17
19 / 100
 262 ms 432 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;

bool check(int x,int y){
	vector <int> M(n);
	M[x] = 1;
	M[y] = 1;
	
	return (Query(M) == 1);
}

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 l = 0,r = N - 1;
	while (l == 0){
		int tot = 0;
		vector <int> M(N);
		for (int i = 0; i < N; i++) {
			M[i] = 1;
			del[i] = 0;
			if (fix[i]) M[i] = 0,del[i] = 1;
			else ++tot;
		}
		
		if (l == r){
			for (int i=0;i<N;i++){
				if (M[i]) {
					ans[l] = i;
					break;
				}
			}
			break;
		}
		
		int cnt = 0;
		while (tot > 0){
			int k;
			while (1){
				k = rnd(N);
				if (del[k]) continue;
				break;
			}
			
			del[k] = 1;
			tot -= 1;
			M[k] = 0;
			if (Query(M) == 1){
				++cnt;
				if (cnt == 1) ans[l] = k;
				else ans[r] = k; 
				fix[k] = 1;
			}
			
			if (cnt == 2) break;
			
			M[k] = 1;
		}
		
		if (l && !check(ans[l - 1],ans[l])){
			swap(ans[l],ans[r]);
		}
		
		l += 1;
		r -= 1;
	}
	
	int val = ans[N - 1];
	
	for (int i = 0; i + 1 < 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++;
			int A = Query(M);
			
			M[ans[i]] = 0;
			ones--;
			int B;
			if (ones == 0) B = 0;
			else B = Query(M);
			
			if (A == B) find |= (1<<j);
		}
		
		fix[find] = 1;
		ans[i + 1] = find;
	}
	
	ans[N - 1] = val;
	for (int i=0;i<N;i++)
		ans[i] += 1;
	Answer(ans);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 344 KB # of queries: 3711
2 Correct 35 ms 344 KB # of queries: 3728
3 Correct 38 ms 344 KB # of queries: 3866
4 Correct 34 ms 344 KB # of queries: 3858
5 Correct 40 ms 344 KB # of queries: 3881
6 Correct 34 ms 344 KB # of queries: 3895
7 Correct 42 ms 344 KB # of queries: 3940
8 Correct 25 ms 344 KB # of queries: 3671
9 Correct 37 ms 344 KB # of queries: 3904
10 Correct 22 ms 344 KB # of queries: 2420
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 13
13 Correct 1 ms 344 KB # of queries: 24
14 Correct 1 ms 344 KB # of queries: 39
15 Correct 2 ms 344 KB # of queries: 210
16 Correct 3 ms 344 KB # of queries: 430

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 344 KB # of queries: 3711
2 Correct 35 ms 344 KB # of queries: 3728
3 Correct 38 ms 344 KB # of queries: 3866
4 Correct 34 ms 344 KB # of queries: 3858
5 Correct 40 ms 344 KB # of queries: 3881
6 Correct 34 ms 344 KB # of queries: 3895
7 Correct 42 ms 344 KB # of queries: 3940
8 Correct 25 ms 344 KB # of queries: 3671
9 Correct 37 ms 344 KB # of queries: 3904
10 Correct 22 ms 344 KB # of queries: 2420
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 13
13 Correct 1 ms 344 KB # of queries: 24
14 Correct 1 ms 344 KB # of queries: 39
15 Correct 2 ms 344 KB # of queries: 210
16 Correct 3 ms 344 KB # of queries: 430
17 Runtime error 262 ms 432 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -