#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, valL[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++) {
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
200 KB |
Output is not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
328 KB |
Output is not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
