oj.uz

답안 #402801

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402801 2021-05-12T11:18:10 Z jamezzz Xoractive (IZhO19_xoractive) C++14
100 / 100
 9 ms 524 KB 
#include "interactive.h"
#include <bits/stdc++.h>
using namespace std;

int val;

set<int> get(vector<int> v){
	multiset<int> ms;
	set<int> res;
	v.push_back(1);
	for(int x:get_pairwise_xor(v)){
		ms.insert(x);
	}
	v.pop_back();
	for(int x:get_pairwise_xor(v)){
		if(ms.count(x)){
			ms.erase(ms.find(x));
		}
	}
	for(auto it:ms){
		if((it^val)==val)continue;
		res.insert(it^val);
	}
	return res;
}

struct qry{
	int l,r;
	vector<int> v;
};

vector<int> ans;
vector<qry> v[2];

vector<int> guess(int n){
	ans.resize(n);
	val=ask(1);
	ans[0]=val;
	int f=0;
	bool done=false;
	v[f].push_back({2,n});
	while(true){
		vector<int> ask;
		for(qry &q:v[f]){
			if(q.l==q.r&&q.v.size()!=0){
				ans[q.l-1]=q.v[0];
				continue;
			}
			for(int i=q.l;i<=(q.l+q.r)/2;++i)ask.push_back(i);
		}
		if(ask.size()==0)break;
		set<int> res=get(ask);
		for(qry &q:v[f]){
			if(q.v.size()==0){
				qry l={q.l,(q.l+q.r)/2},r={(q.l+q.r)/2+1,q.r};
				for(auto x:res){
					l.v.push_back(x);
				}
				if(l.l<=l.r)v[1-f].push_back(l);
				if(q.l!=q.r)v[1-f].push_back(r);
			}
			else{
				if(q.l==q.r&&q.v.size()!=0)continue;
				qry l={q.l,(q.l+q.r)/2},r={(q.l+q.r)/2+1,q.r};
				for(int x:q.v){
					if(res.find(x)!=res.end())l.v.push_back(x),res.erase(x);
					else r.v.push_back(x);
				}
				if(l.l<=l.r)v[1-f].push_back(l);
				if(r.l<=r.r)v[1-f].push_back(r);
			}
		}
		v[f].clear();
		f=1-f;
	}
	f=1-f;
	return ans;
}

Compilation message

Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:40:7: warning: unused variable 'done' [-Wunused-variable]
   40 |  bool done=false;
      |       ^~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct

Subtask #2
94.0 / 94.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 456 KB Output is correct
2 Correct 7 ms 432 KB Output is correct
3 Correct 7 ms 456 KB Output is correct
4 Correct 9 ms 456 KB Output is correct
5 Correct 7 ms 456 KB Output is correct
6 Correct 7 ms 456 KB Output is correct
7 Correct 7 ms 456 KB Output is correct
8 Correct 7 ms 456 KB Output is correct
9 Correct 7 ms 456 KB Output is correct
10 Correct 7 ms 432 KB Output is correct
11 Correct 7 ms 432 KB Output is correct
12 Correct 7 ms 424 KB Output is correct
13 Correct 7 ms 456 KB Output is correct
14 Correct 7 ms 456 KB Output is correct
15 Correct 8 ms 456 KB Output is correct
16 Correct 8 ms 456 KB Output is correct
17 Correct 7 ms 456 KB Output is correct
18 Correct 7 ms 456 KB Output is correct
19 Correct 7 ms 456 KB Output is correct
20 Correct 7 ms 456 KB Output is correct
21 Correct 8 ms 492 KB Output is correct
22 Correct 7 ms 440 KB Output is correct
23 Correct 7 ms 456 KB Output is correct
24 Correct 8 ms 456 KB Output is correct
25 Correct 7 ms 456 KB Output is correct
26 Correct 7 ms 456 KB Output is correct
27 Correct 7 ms 456 KB Output is correct
28 Correct 7 ms 456 KB Output is correct
29 Correct 7 ms 456 KB Output is correct
30 Correct 7 ms 456 KB Output is correct
31 Correct 7 ms 456 KB Output is correct
32 Correct 7 ms 456 KB Output is correct
33 Correct 7 ms 456 KB Output is correct
34 Correct 7 ms 456 KB Output is correct
35 Correct 8 ms 456 KB Output is correct
36 Correct 7 ms 456 KB Output is correct
37 Correct 7 ms 456 KB Output is correct
38 Correct 7 ms 456 KB Output is correct
39 Correct 7 ms 456 KB Output is correct
40 Correct 7 ms 456 KB Output is correct
41 Correct 7 ms 456 KB Output is correct
42 Correct 7 ms 456 KB Output is correct
43 Correct 7 ms 520 KB Output is correct
44 Correct 7 ms 456 KB Output is correct
45 Correct 7 ms 444 KB Output is correct
46 Correct 7 ms 456 KB Output is correct
47 Correct 7 ms 428 KB Output is correct
48 Correct 8 ms 456 KB Output is correct
49 Correct 7 ms 456 KB Output is correct
50 Correct 7 ms 456 KB Output is correct
51 Correct 8 ms 456 KB Output is correct
52 Correct 8 ms 468 KB Output is correct
53 Correct 7 ms 456 KB Output is correct
54 Correct 7 ms 456 KB Output is correct
55 Correct 7 ms 456 KB Output is correct
56 Correct 8 ms 456 KB Output is correct
57 Correct 7 ms 456 KB Output is correct
58 Correct 7 ms 456 KB Output is correct
59 Correct 7 ms 456 KB Output is correct
60 Correct 7 ms 456 KB Output is correct
61 Correct 7 ms 456 KB Output is correct
62 Correct 7 ms 456 KB Output is correct
63 Correct 7 ms 524 KB Output is correct
64 Correct 7 ms 456 KB Output is correct
65 Correct 8 ms 444 KB Output is correct
66 Correct 8 ms 456 KB Output is correct
67 Correct 7 ms 456 KB Output is correct
68 Correct 7 ms 516 KB Output is correct
69 Correct 7 ms 456 KB Output is correct
70 Correct 7 ms 440 KB Output is correct
71 Correct 7 ms 456 KB Output is correct
72 Correct 7 ms 472 KB Output is correct
73 Correct 7 ms 456 KB Output is correct
74 Correct 7 ms 456 KB Output is correct
75 Correct 8 ms 444 KB Output is correct
76 Correct 7 ms 456 KB Output is correct
77 Correct 7 ms 476 KB Output is correct
78 Correct 7 ms 456 KB Output is correct
79 Correct 7 ms 456 KB Output is correct
80 Correct 7 ms 456 KB Output is correct
81 Correct 7 ms 456 KB Output is correct
82 Correct 7 ms 456 KB Output is correct
83 Correct 7 ms 508 KB Output is correct
84 Correct 7 ms 436 KB Output is correct
85 Correct 9 ms 436 KB Output is correct
86 Correct 7 ms 456 KB Output is correct
87 Correct 7 ms 456 KB Output is correct
88 Correct 9 ms 436 KB Output is correct
89 Correct 9 ms 456 KB Output is correct
90 Correct 9 ms 456 KB Output is correct
91 Correct 8 ms 444 KB Output is correct
92 Correct 7 ms 456 KB Output is correct
93 Correct 9 ms 456 KB Output is correct
94 Correct 7 ms 456 KB Output is correct
95 Correct 8 ms 456 KB Output is correct
96 Correct 7 ms 456 KB Output is correct
97 Correct 7 ms 456 KB Output is correct
98 Correct 7 ms 456 KB Output is correct
99 Correct 7 ms 456 KB Output is correct
100 Correct 8 ms 456 KB Output is correct