oj.uz

Submission #503474

# Submission time Handle Problem Language Result Execution time Memory
503474 2022-01-08T07:05:26 Z Gurban Xoractive (IZhO19_xoractive) C++17
88 / 100
 8 ms 912 KB 
#include "bits/stdc++.h"
#include "interactive.h"
using namespace std;

const int maxn=105;
int a[maxn];
int lft[4*maxn],rgt[4*maxn];
set<int>arr[4*maxn];
vector<int>fn;
map<int,vector<int>>m;

void f(int l,int r,int nd,int lev){
	lft[nd] = l;
	rgt[nd] = r;
	m[lev].push_back(nd);
	if(l == r){
		fn.push_back(nd);
		return;
	}
	int md = (l + r) / 2;
	f(l,md,nd*2,lev+1);
	f(md+1,r,nd*2+1,lev+1);
}

set<int>A(vector<int>v){
	if(v.empty()) return set<int>();
	
	// for(auto i : v) cout<<i<<' ';
	// cout<<" ----> ";

	vector<int>now = v;
	now.push_back(1);

	vector<int>nw = get_pairwise_xor(now);
	vector<int>z = get_pairwise_xor(v);

	// for(auto i : nw) cout<<i<<' ';
	// cout<<" ----> ";
	// for(auto i : z) cout<<i<<' ';
	// cout<<" ----> ";

	multiset<int>SS(nw.begin(),nw.end());
	for(auto i : z) SS.erase(SS.find(i));

	// for(auto i : SS) cout<<i<<' ';
	// cout<<" ---> ";

	set<int>jg;
	for(auto i : SS) jg.insert(i ^ a[1]);
	jg.erase(a[1]);
	
	// for(auto i : jg) cout<<i<<' ';
	// cout<<'\n';

	return jg;
}

vector<int> guess(int n) {
	a[1] = ask(1);
	f(2,n,1,1);
	vector<int>go;
	for(int i = 2;i <= n;i++) go.push_back(i);
	arr[1] = A(go);
	for(auto i : m){
		if(i.first == 1) continue;
		vector<int>now;
		for(auto j : i.second){
			if(!(j & 1)) for(int k = lft[j];k <= rgt[j];k++){
				now.push_back(k);
			}
		}
		set<int>sw = A(now);
		for(auto j : i.second){
			if(j & 1){
				arr[j] = arr[(j-1)/2];
				for(auto l : arr[j-1]) arr[j].erase(l);
			}
			else {
				for(auto l : arr[j/2]) if(sw.find(l) != sw.end()) arr[j].insert(l);
			}
		}
	}
	// for(int i = 1;i <= 2*n;i++){
	// 	cout<<i<<' '<<lft[i]<<' '<<rgt[i]<<" ----> ";
	// 	for(auto j : arr[i]) cout<<j<<' ';
	// 	cout<<'\n';
	// }
	vector<int>ans; ans.push_back(a[1]);
	for(auto i : fn){
		if(!arr[i].empty()) ans.push_back(*arr[i].begin());
	}
	return ans;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct

Subtask #2
82.0 / 94.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 840 KB Output is partially correct
2 Partially correct 7 ms 840 KB Output is partially correct
3 Partially correct 6 ms 840 KB Output is partially correct
4 Partially correct 7 ms 908 KB Output is partially correct
5 Partially correct 7 ms 840 KB Output is partially correct
6 Partially correct 7 ms 876 KB Output is partially correct
7 Partially correct 6 ms 840 KB Output is partially correct
8 Partially correct 6 ms 840 KB Output is partially correct
9 Partially correct 7 ms 840 KB Output is partially correct
10 Partially correct 7 ms 840 KB Output is partially correct
11 Partially correct 5 ms 840 KB Output is partially correct
12 Partially correct 7 ms 840 KB Output is partially correct
13 Partially correct 6 ms 840 KB Output is partially correct
14 Partially correct 7 ms 864 KB Output is partially correct
15 Partially correct 6 ms 852 KB Output is partially correct
16 Partially correct 7 ms 840 KB Output is partially correct
17 Partially correct 6 ms 840 KB Output is partially correct
18 Partially correct 6 ms 840 KB Output is partially correct
19 Partially correct 6 ms 836 KB Output is partially correct
20 Partially correct 7 ms 840 KB Output is partially correct
21 Partially correct 7 ms 872 KB Output is partially correct
22 Partially correct 8 ms 840 KB Output is partially correct
23 Partially correct 7 ms 840 KB Output is partially correct
24 Partially correct 7 ms 844 KB Output is partially correct
25 Partially correct 6 ms 860 KB Output is partially correct
26 Partially correct 6 ms 840 KB Output is partially correct
27 Partially correct 7 ms 844 KB Output is partially correct
28 Partially correct 6 ms 840 KB Output is partially correct
29 Partially correct 7 ms 840 KB Output is partially correct
30 Partially correct 7 ms 840 KB Output is partially correct
31 Partially correct 7 ms 840 KB Output is partially correct
32 Partially correct 7 ms 840 KB Output is partially correct
33 Partially correct 6 ms 840 KB Output is partially correct
34 Partially correct 7 ms 840 KB Output is partially correct
35 Partially correct 6 ms 840 KB Output is partially correct
36 Partially correct 6 ms 876 KB Output is partially correct
37 Partially correct 6 ms 860 KB Output is partially correct
38 Partially correct 7 ms 840 KB Output is partially correct
39 Partially correct 6 ms 840 KB Output is partially correct
40 Partially correct 7 ms 868 KB Output is partially correct
41 Partially correct 6 ms 840 KB Output is partially correct
42 Partially correct 8 ms 856 KB Output is partially correct
43 Partially correct 6 ms 840 KB Output is partially correct
44 Partially correct 7 ms 856 KB Output is partially correct
45 Partially correct 7 ms 840 KB Output is partially correct
46 Partially correct 6 ms 840 KB Output is partially correct
47 Partially correct 6 ms 880 KB Output is partially correct
48 Partially correct 7 ms 840 KB Output is partially correct
49 Partially correct 6 ms 840 KB Output is partially correct
50 Partially correct 6 ms 840 KB Output is partially correct
51 Partially correct 6 ms 840 KB Output is partially correct
52 Partially correct 6 ms 824 KB Output is partially correct
53 Partially correct 7 ms 840 KB Output is partially correct
54 Partially correct 7 ms 840 KB Output is partially correct
55 Partially correct 6 ms 840 KB Output is partially correct
56 Partially correct 7 ms 840 KB Output is partially correct
57 Partially correct 7 ms 844 KB Output is partially correct
58 Partially correct 7 ms 840 KB Output is partially correct
59 Partially correct 6 ms 840 KB Output is partially correct
60 Partially correct 6 ms 840 KB Output is partially correct
61 Partially correct 6 ms 840 KB Output is partially correct
62 Partially correct 7 ms 856 KB Output is partially correct
63 Partially correct 6 ms 884 KB Output is partially correct
64 Partially correct 6 ms 856 KB Output is partially correct
65 Partially correct 7 ms 912 KB Output is partially correct
66 Partially correct 6 ms 856 KB Output is partially correct
67 Partially correct 6 ms 840 KB Output is partially correct
68 Partially correct 7 ms 856 KB Output is partially correct
69 Partially correct 7 ms 856 KB Output is partially correct
70 Partially correct 6 ms 856 KB Output is partially correct
71 Partially correct 6 ms 840 KB Output is partially correct
72 Partially correct 6 ms 840 KB Output is partially correct
73 Partially correct 7 ms 840 KB Output is partially correct
74 Partially correct 6 ms 860 KB Output is partially correct
75 Partially correct 7 ms 840 KB Output is partially correct
76 Partially correct 7 ms 840 KB Output is partially correct
77 Partially correct 7 ms 840 KB Output is partially correct
78 Partially correct 7 ms 880 KB Output is partially correct
79 Partially correct 6 ms 840 KB Output is partially correct
80 Partially correct 7 ms 840 KB Output is partially correct
81 Partially correct 7 ms 840 KB Output is partially correct
82 Partially correct 7 ms 840 KB Output is partially correct
83 Partially correct 8 ms 840 KB Output is partially correct
84 Partially correct 8 ms 892 KB Output is partially correct
85 Partially correct 6 ms 840 KB Output is partially correct
86 Partially correct 7 ms 872 KB Output is partially correct
87 Partially correct 6 ms 840 KB Output is partially correct
88 Partially correct 7 ms 840 KB Output is partially correct
89 Partially correct 7 ms 840 KB Output is partially correct
90 Partially correct 7 ms 836 KB Output is partially correct
91 Partially correct 6 ms 840 KB Output is partially correct
92 Partially correct 6 ms 840 KB Output is partially correct
93 Partially correct 7 ms 840 KB Output is partially correct
94 Partially correct 7 ms 900 KB Output is partially correct
95 Partially correct 6 ms 848 KB Output is partially correct
96 Partially correct 6 ms 848 KB Output is partially correct
97 Partially correct 7 ms 904 KB Output is partially correct
98 Partially correct 7 ms 848 KB Output is partially correct
99 Partially correct 7 ms 848 KB Output is partially correct
100 Partially correct 7 ms 848 KB Output is partially correct