#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "interactive.h"
const int MAX_N = 18;
vector<int> operator +(vector<int> a, vector<int> b) { a.insert(end(a), AI(b)); return a; }
vector<int> operator &(vector<int> a, vector<int> b) {
map<int,int> cnt;
for (auto i : a) ++cnt[i];
vector<int> res;
for (auto i : b) if (cnt[i])
res.pb(i), --cnt[i];
sort(AI(res));
return res;
}
vector<int> operator -(vector<int> a, vector<int> b) {
map<int, int> cnt;
for (auto i : a) ++cnt[i];
for (auto i : b) --cnt[i];
vector<int> res;
for (auto [v, c] : cnt)
while (c--) res.pb(v);
return res;
}
int qcnt;
vector<int> ans;
// vector<int> get_pairwise_xor(vector<int>);
vector<int> get_values(vector<int> ids) {
cerr << "get values at index: ";
debug(AI(ids));
auto allid = get_pairwise_xor(ids);
auto id1 = ids;
id1.pb(1);
auto with1 = get_pairwise_xor(id1);
auto onewithid = with1 - allid;
sort(AI(onewithid));
vector<int> res;
for (int i = 2;i < onewithid.size();i += 2)
res.pb(onewithid[i] ^ ans[0]);
debug(AI(res));
qcnt += 2;
return res;
}
vector<int> have[MAX_N][2];
vector<int> guess(int n) {
ans.pb(ask(1));
if (n <= 15) {
for (int i = 2;i <= n;++i)
ans.pb(ask(i));
return ans;
}
vector<int> allvalue(n-1); iota(AI(allvalue), 2);
allvalue = get_values(allvalue);
int lg = 6;
for (int d = 0;d < lg;++d) {
vector<int> no, yes;
for (int i = 1;i < n;++i)
((i>>d&1) ? yes : no).pb(i+1);
have[d][0]=(get_values(no));
have[d][1] = allvalue - have[d][0];
//have[d][1]=(get_values(yes));
}
for (int i = 1;i < n;++i) {
auto cand = have[0][0] + have[0][1];
for (int d = 0;d < lg;++d)
cand = cand & have[d][i>>d&1];
if (cand.size() > 1)
ans.pb(ask(i+1));
else
ans.pb(cand[0]);
DE(i, cand[0]);
}
DE(qcnt, n);
return ans;
}
Compilation message
Xoractive.cpp: In function 'std::vector<int> get_values(std::vector<int>)':
Xoractive.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
Xoractive.cpp:51:2: note: in expansion of macro 'debug'
51 | debug(AI(ids));
| ^~~~~
Xoractive.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int i = 2;i < onewithid.size();i += 2)
| ~~^~~~~~~~~~~~~~~~~~
Xoractive.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
Xoractive.cpp:67:2: note: in expansion of macro 'debug'
67 | debug(AI(res));
| ^~~~~
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
Xoractive.cpp:112:3: note: in expansion of macro 'DE'
112 | DE(i, cand[0]);
| ^~
Xoractive.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
Xoractive.cpp:115:2: note: in expansion of macro 'DE'
115 | DE(qcnt, n);
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
