Submission #502608

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
502608	2022-01-06T10:33:57 Z	Mazaalai	Xoractive (IZhO19_xoractive)	C++17	88 / 100	4 ms	456 KB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define LINE "------------------\n"
#define ALL(x) x.begin(),x.end()
#define print(x) for(auto&el:x)cout<<el<<' ';cout<<'\n';
using namespace std;
using VI = vector <int>;
const int N = 105;
vector <int> ans;
int a1, n, answered;
// get_pairwise_xor, ask
VI getDif(vector <int>&a, vector <int>&b) {
	int i = 0, j = 0, x = a.size(), y = b.size();
	vector <int> res;
	while(i < x) {
		if (j < y && a[i] == b[j]) {
			i++, j++;
			continue;
		}
		res.pb(a[i++]);
	}
	return res;
}
VI getVals (VI ids) {
	VI ids1 = ids;
	ids1.pb(1);
	VI res = get_pairwise_xor(ids1);
	VI res1 = get_pairwise_xor(ids);
	VI vals = getDif(res, res1), ret;
	for (int i = 1; i < vals.size(); i+=2) ret.pb(vals[i]^a1);
	return ret;
}
void assign(int pos, int val) {
	answered++;
	ans[pos]=val;
}
vector<int> guess(int _n) {
	n = _n;
	a1 = ask(1);
	ans.resize(n);
	assign(0, a1); 
	vector <vector <pair <VI, VI> > >lvls(30);
	{
		VI ids, vals;
		for (int i = 2; i <= n; i++) ids.pb(i);
		vals = getVals(ids);
		lvls[0].pb(mp(ids, vals));
	}
	for (int lvl = 0; answered < n; lvl++) {
		VI queryIds;
		map <int, bool> isLeft;
		// divide;
		// cout << LINE;
		for (int i = 0; i < lvls[lvl].size(); i++) {
			VI& ids = lvls[lvl][i].ff;
			VI& vals = lvls[lvl][i].ss;
			// cout << "ids: "; print(ids);
			// cout << "vals: "; print(vals);
			// cout << '\n';
			int curSz = ids.size();
			for (int j = 0; j < curSz/2; j++) 
				queryIds.pb(ids[j]);
		}
		// find elements on the left side
		{
			// cout << "queryIds: ";print(queryIds);
			VI vals = getVals(queryIds);
			for (auto&el : vals) isLeft[el] = 1;

		}

		for (int i = 0; i < lvls[lvl].size(); i++) {
			VI& ids = lvls[lvl][i].ff;
			VI& vals = lvls[lvl][i].ss;
			VI lhs, rhs, valL, valR;
			int curSz = ids.size();
			// cout << "ids: "; print(ids);
			// cout << "vals: "; print(vals);
			for (int j = 0; j < curSz/2; j++) 
				lhs.pb(ids[j]);
			for (int j = curSz/2; j < curSz; j++) 
				rhs.pb(ids[j]);
			for (int j = 0; j < curSz; j++) {
				if (isLeft.count(vals[j])) valL.pb(vals[j]);
				else valR.pb(vals[j]);
			}
			// cout << "lhs: "; print(lhs);
			// cout << "valL: "; print(valL);
			// cout << "rhs: "; print(rhs);
			// cout << "valR: "; print(valR);
			if (lhs.size() == 1) assign(lhs[0]-1, valL[0]);
			else lvls[lvl+1].pb(mp(lhs, valL));
			if (rhs.size() == 1) assign(rhs[0]-1, valR[0]);
			else lvls[lvl+1].pb(mp(rhs, valR));
		}

	}
	// vals, ids -> vector <int> vals, vector <int> ids
	return ans;
}

Compilation message

Xoractive.cpp: In function 'VI getVals(VI)':
Xoractive.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int i = 1; i < vals.size(); i+=2) ret.pb(vals[i]^a1);
      |                  ~~^~~~~~~~~~~~~
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::vector<int>, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (int i = 0; i < lvls[lvl].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~
Xoractive.cpp:60:8: warning: unused variable 'vals' [-Wunused-variable]
   60 |    VI& vals = lvls[lvl][i].ss;
      |        ^~~~
Xoractive.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::vector<int>, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for (int i = 0; i < lvls[lvl].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~

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	4 ms	404 KB	Output is partially correct
2	Partially correct	3 ms	404 KB	Output is partially correct
3	Partially correct	2 ms	328 KB	Output is partially correct
4	Partially correct	3 ms	328 KB	Output is partially correct
5	Partially correct	3 ms	328 KB	Output is partially correct
6	Partially correct	3 ms	408 KB	Output is partially correct
7	Partially correct	3 ms	328 KB	Output is partially correct
8	Partially correct	3 ms	328 KB	Output is partially correct
9	Partially correct	3 ms	328 KB	Output is partially correct
10	Partially correct	3 ms	328 KB	Output is partially correct
11	Partially correct	3 ms	328 KB	Output is partially correct
12	Partially correct	3 ms	328 KB	Output is partially correct
13	Partially correct	4 ms	428 KB	Output is partially correct
14	Partially correct	3 ms	328 KB	Output is partially correct
15	Partially correct	4 ms	328 KB	Output is partially correct
16	Partially correct	3 ms	328 KB	Output is partially correct
17	Partially correct	3 ms	328 KB	Output is partially correct
18	Partially correct	3 ms	328 KB	Output is partially correct
19	Partially correct	2 ms	408 KB	Output is partially correct
20	Partially correct	3 ms	328 KB	Output is partially correct
21	Partially correct	3 ms	328 KB	Output is partially correct
22	Partially correct	3 ms	328 KB	Output is partially correct
23	Partially correct	3 ms	328 KB	Output is partially correct
24	Partially correct	4 ms	328 KB	Output is partially correct
25	Partially correct	3 ms	328 KB	Output is partially correct
26	Partially correct	3 ms	328 KB	Output is partially correct
27	Partially correct	2 ms	328 KB	Output is partially correct
28	Partially correct	3 ms	328 KB	Output is partially correct
29	Partially correct	3 ms	404 KB	Output is partially correct
30	Partially correct	3 ms	328 KB	Output is partially correct
31	Partially correct	3 ms	400 KB	Output is partially correct
32	Partially correct	3 ms	328 KB	Output is partially correct
33	Partially correct	3 ms	328 KB	Output is partially correct
34	Partially correct	3 ms	396 KB	Output is partially correct
35	Partially correct	2 ms	328 KB	Output is partially correct
36	Partially correct	3 ms	328 KB	Output is partially correct
37	Partially correct	3 ms	328 KB	Output is partially correct
38	Partially correct	3 ms	328 KB	Output is partially correct
39	Partially correct	2 ms	328 KB	Output is partially correct
40	Partially correct	3 ms	328 KB	Output is partially correct
41	Partially correct	3 ms	328 KB	Output is partially correct
42	Partially correct	3 ms	328 KB	Output is partially correct
43	Partially correct	2 ms	328 KB	Output is partially correct
44	Partially correct	3 ms	328 KB	Output is partially correct
45	Partially correct	3 ms	328 KB	Output is partially correct
46	Partially correct	3 ms	328 KB	Output is partially correct
47	Partially correct	2 ms	328 KB	Output is partially correct
48	Partially correct	3 ms	328 KB	Output is partially correct
49	Partially correct	3 ms	328 KB	Output is partially correct
50	Partially correct	3 ms	328 KB	Output is partially correct
51	Partially correct	2 ms	328 KB	Output is partially correct
52	Partially correct	3 ms	400 KB	Output is partially correct
53	Partially correct	3 ms	412 KB	Output is partially correct
54	Partially correct	3 ms	404 KB	Output is partially correct
55	Partially correct	2 ms	328 KB	Output is partially correct
56	Partially correct	3 ms	328 KB	Output is partially correct
57	Partially correct	4 ms	328 KB	Output is partially correct
58	Partially correct	3 ms	412 KB	Output is partially correct
59	Partially correct	3 ms	396 KB	Output is partially correct
60	Partially correct	3 ms	404 KB	Output is partially correct
61	Partially correct	3 ms	328 KB	Output is partially correct
62	Partially correct	3 ms	328 KB	Output is partially correct
63	Partially correct	3 ms	328 KB	Output is partially correct
64	Partially correct	3 ms	328 KB	Output is partially correct
65	Partially correct	3 ms	328 KB	Output is partially correct
66	Partially correct	3 ms	328 KB	Output is partially correct
67	Partially correct	3 ms	328 KB	Output is partially correct
68	Partially correct	3 ms	328 KB	Output is partially correct
69	Partially correct	3 ms	328 KB	Output is partially correct
70	Partially correct	3 ms	384 KB	Output is partially correct
71	Partially correct	4 ms	328 KB	Output is partially correct
72	Partially correct	3 ms	328 KB	Output is partially correct
73	Partially correct	3 ms	328 KB	Output is partially correct
74	Partially correct	3 ms	328 KB	Output is partially correct
75	Partially correct	3 ms	328 KB	Output is partially correct
76	Partially correct	3 ms	328 KB	Output is partially correct
77	Partially correct	3 ms	328 KB	Output is partially correct
78	Partially correct	3 ms	328 KB	Output is partially correct
79	Partially correct	2 ms	328 KB	Output is partially correct
80	Partially correct	3 ms	328 KB	Output is partially correct
81	Partially correct	3 ms	456 KB	Output is partially correct
82	Partially correct	3 ms	392 KB	Output is partially correct
83	Partially correct	2 ms	408 KB	Output is partially correct
84	Partially correct	3 ms	408 KB	Output is partially correct
85	Partially correct	3 ms	328 KB	Output is partially correct
86	Partially correct	3 ms	328 KB	Output is partially correct
87	Partially correct	2 ms	328 KB	Output is partially correct
88	Partially correct	3 ms	328 KB	Output is partially correct
89	Partially correct	3 ms	328 KB	Output is partially correct
90	Partially correct	3 ms	328 KB	Output is partially correct
91	Partially correct	2 ms	328 KB	Output is partially correct
92	Partially correct	3 ms	328 KB	Output is partially correct
93	Partially correct	3 ms	328 KB	Output is partially correct
94	Partially correct	3 ms	328 KB	Output is partially correct
95	Partially correct	2 ms	328 KB	Output is partially correct
96	Partially correct	3 ms	392 KB	Output is partially correct
97	Partially correct	3 ms	384 KB	Output is partially correct
98	Partially correct	3 ms	328 KB	Output is partially correct
99	Partially correct	2 ms	328 KB	Output is partially correct
100	Partially correct	3 ms	328 KB	Output is partially correct