Submission #894580

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
894580	2023-12-28T13:13:44 Z	mychecksedad	Xoractive (IZhO19_xoractive)	C++17	100 / 100	4 ms	596 KB

Xoractive

#include "interactive.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
int ask(int x);
vector<int> get_pairwise_xor(vector<int> positions);

int x;
map<int, vector<int>> p;
vector<int> dif(vector<int> a, vector<int> b){
	for(int i = 0; i < a.size(); ++i){
		int pos = lower_bound(all(b), a[i]) - b.begin();
		b.erase(b.begin() + pos);
	}
	// b.erase(b.begin());
	return b;
}
vector<int> get(vector<int> pos){
	vector<int> v = get_pairwise_xor(pos);
	vector<int> t;
	for(int i = int(sqrt(v.size())); i < v.size(); i += 2) t.pb(v[i]);
	return t;	
}
vector<int> learn_sorted(vector<int> v){
	vector<int> s1 = get(v);
	v.pb(1);
	vector<int> s2 = get(v);
	return dif(s1, s2);
}
set<int> s;
vector<int> guess(int n) {
	// cout << n << ' ' << "brh\n";
	vector <int> ans;

	x = ask(1);
	ans.pb(x);

	vector<int> pos;
	for(int j = 6; j >= 0; --j){
		pos.clear();
		for(int i = 2; i <= n; ++i){
			if(((i-2)&(1<<j)) == 0){
				pos.pb(i);
			}
		}
		vector<int> v = learn_sorted(pos);
		// for(int y: v) cout << y << ' ';
		// en;
		for(auto &y: v) y ^= x;
			// for(int y: v) cout << y << ' ';
			// en;
		for(int i = 0; i < v.size(); ++i) p[v[i]].pb(j), s.insert(v[i]);
	}
	// cout << x << ' ';
	vector<int> A;
	// for(auto y: A) cout << y << ' ' ;
	// cout << endl;
	for(int k: s) A.pb(k);
	sort(all(A), [&](const int &a, const int &b){
		for(int j = 0; j < p[a].size(); ++j){
			if(p[b].size() == j) return true;
			if(p[a][j] != p[b][j]) return p[a][j] > p[b][j];
		}
		// assert(false);
		return false;
	});
	for(int x: A) ans.pb(x);
	return ans;
}

Compilation message

Xoractive.cpp: In function 'std::vector<int> dif(std::vector<int>, std::vector<int>)':
Xoractive.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0; i < a.size(); ++i){
      |                 ~~^~~~~~~~~~
Xoractive.cpp: In function 'std::vector<int> get(std::vector<int>)':
Xoractive.cpp:26:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = int(sqrt(v.size())); i < v.size(); i += 2) t.pb(v[i]);
      |                                   ~~^~~~~~~~~~
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int i = 0; i < v.size(); ++i) p[v[i]].pb(j), s.insert(v[i]);
      |                  ~~^~~~~~~~~~
Xoractive.cpp: In lambda function:
Xoractive.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int j = 0; j < p[a].size(); ++j){
      |                  ~~^~~~~~~~~~~~~
Xoractive.cpp:66:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |    if(p[b].size() == j) return true;
      |       ~~~~~~~~~~~~^~~~

Subtask #1
6.0 / 6.0

#	Verdict	Memory	Grader output
1	Correct	356 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	344 KB	Output is correct
4	Correct	344 KB	Output is correct

Subtask #2
94.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	344 KB	Output is correct
2	Correct	3 ms	344 KB	Output is correct
3	Correct	2 ms	492 KB	Output is correct
4	Correct	3 ms	344 KB	Output is correct
5	Correct	3 ms	344 KB	Output is correct
6	Correct	3 ms	344 KB	Output is correct
7	Correct	3 ms	504 KB	Output is correct
8	Correct	3 ms	344 KB	Output is correct
9	Correct	3 ms	344 KB	Output is correct
10	Correct	3 ms	496 KB	Output is correct
11	Correct	2 ms	344 KB	Output is correct
12	Correct	3 ms	344 KB	Output is correct
13	Correct	3 ms	344 KB	Output is correct
14	Correct	3 ms	344 KB	Output is correct
15	Correct	3 ms	592 KB	Output is correct
16	Correct	3 ms	344 KB	Output is correct
17	Correct	3 ms	344 KB	Output is correct
18	Correct	3 ms	344 KB	Output is correct
19	Correct	3 ms	344 KB	Output is correct
20	Correct	3 ms	344 KB	Output is correct
21	Correct	4 ms	344 KB	Output is correct
22	Correct	3 ms	344 KB	Output is correct
23	Correct	3 ms	344 KB	Output is correct
24	Correct	3 ms	344 KB	Output is correct
25	Correct	3 ms	344 KB	Output is correct
26	Correct	3 ms	344 KB	Output is correct
27	Correct	3 ms	344 KB	Output is correct
28	Correct	3 ms	344 KB	Output is correct
29	Correct	3 ms	344 KB	Output is correct
30	Correct	3 ms	344 KB	Output is correct
31	Correct	3 ms	344 KB	Output is correct
32	Correct	3 ms	344 KB	Output is correct
33	Correct	3 ms	496 KB	Output is correct
34	Correct	3 ms	344 KB	Output is correct
35	Correct	3 ms	344 KB	Output is correct
36	Correct	3 ms	344 KB	Output is correct
37	Correct	3 ms	344 KB	Output is correct
38	Correct	3 ms	344 KB	Output is correct
39	Correct	3 ms	344 KB	Output is correct
40	Correct	3 ms	344 KB	Output is correct
41	Correct	3 ms	344 KB	Output is correct
42	Correct	4 ms	344 KB	Output is correct
43	Correct	3 ms	344 KB	Output is correct
44	Correct	3 ms	344 KB	Output is correct
45	Correct	3 ms	596 KB	Output is correct
46	Correct	3 ms	344 KB	Output is correct
47	Correct	2 ms	344 KB	Output is correct
48	Correct	3 ms	500 KB	Output is correct
49	Correct	3 ms	344 KB	Output is correct
50	Correct	3 ms	344 KB	Output is correct
51	Correct	2 ms	344 KB	Output is correct
52	Correct	3 ms	344 KB	Output is correct
53	Correct	3 ms	344 KB	Output is correct
54	Correct	3 ms	344 KB	Output is correct
55	Correct	2 ms	344 KB	Output is correct
56	Correct	3 ms	344 KB	Output is correct
57	Correct	3 ms	344 KB	Output is correct
58	Correct	3 ms	344 KB	Output is correct
59	Correct	3 ms	500 KB	Output is correct
60	Correct	3 ms	344 KB	Output is correct
61	Correct	3 ms	344 KB	Output is correct
62	Correct	3 ms	344 KB	Output is correct
63	Correct	2 ms	344 KB	Output is correct
64	Correct	3 ms	344 KB	Output is correct
65	Correct	3 ms	344 KB	Output is correct
66	Correct	3 ms	344 KB	Output is correct
67	Correct	3 ms	344 KB	Output is correct
68	Correct	3 ms	344 KB	Output is correct
69	Correct	3 ms	512 KB	Output is correct
70	Correct	3 ms	344 KB	Output is correct
71	Correct	3 ms	344 KB	Output is correct
72	Correct	3 ms	420 KB	Output is correct
73	Correct	3 ms	344 KB	Output is correct
74	Correct	3 ms	344 KB	Output is correct
75	Correct	3 ms	344 KB	Output is correct
76	Correct	3 ms	344 KB	Output is correct
77	Correct	3 ms	344 KB	Output is correct
78	Correct	3 ms	344 KB	Output is correct
79	Correct	2 ms	344 KB	Output is correct
80	Correct	3 ms	344 KB	Output is correct
81	Correct	3 ms	344 KB	Output is correct
82	Correct	3 ms	344 KB	Output is correct
83	Correct	2 ms	344 KB	Output is correct
84	Correct	3 ms	344 KB	Output is correct
85	Correct	3 ms	344 KB	Output is correct
86	Correct	3 ms	344 KB	Output is correct
87	Correct	4 ms	344 KB	Output is correct
88	Correct	3 ms	348 KB	Output is correct
89	Correct	3 ms	344 KB	Output is correct
90	Correct	3 ms	344 KB	Output is correct
91	Correct	3 ms	344 KB	Output is correct
92	Correct	3 ms	344 KB	Output is correct
93	Correct	3 ms	384 KB	Output is correct
94	Correct	3 ms	344 KB	Output is correct
95	Correct	2 ms	344 KB	Output is correct
96	Correct	3 ms	352 KB	Output is correct
97	Correct	3 ms	344 KB	Output is correct
98	Correct	3 ms	344 KB	Output is correct
99	Correct	3 ms	356 KB	Output is correct
100	Correct	3 ms	504 KB	Output is correct

Submission #894580

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 94.0 / 94.0

Subtask #1
6.0 / 6.0

Subtask #2
94.0 / 94.0