#include "interactive.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define debug(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 pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }
vector<int> guess(int n) {
vector <int> G;
vector <int> ans(n);
if (n <= 1) {
for (int i = 1; i <= n; i++)
ans[i-1] = ask(i);
return ans;
}
for (int i = 2; i <= n; i++)
G.pb(i);
vector <int> exp = get_pairwise_xor(G);
G.pb(1);
vector <int> all = get_pairwise_xor(G);
set <int> nums;
vector <int> arr, pos(n);
ans[0] = ask(1);
int j = 0;
for (int i = 0; i < exp.size(); i++, j++)
while (all[j] != exp[i])
nums.insert(all[j++] ^ ans[0]);
while (j < all.size()) nums.insert(all[j++] ^ ans[0]);
for (int i : nums) arr.pb(i);
srand(time(NULL));
random_shuffle(arr.begin(), arr.end());
for (int i = 0; (1<<i) < n; i++) {
G.clear();
for (int j = 0; j < n; j++)
if (!(j&(1<<i))) G.pb(j+1);
pary(G.begin(), G.end());
vector <int> res = get_pairwise_xor(G);
vector <int> tmp, nxt;
for (int j = 0; j < n; j++) tmp.pb(j);
while (tmp.size() > G.size()) {
for (int j : tmp) {
int cnt = 0;
for (int k : tmp) {
int val = arr[j] ^ arr[k];
if (res[res.size()-1] >= val && *lower_bound(res.begin(), res.end(), val) == val)
cnt++;
}
if (cnt >= G.size()) nxt.pb(j);
}
if (tmp.size() == nxt.size()) break;
tmp = nxt;
nxt.clear();
}
vector <int> rand(tmp.size());
for (int j = 0; j < tmp.size(); j++)
rand[j] = j;
int C = 0;
while (tmp.size() > G.size()) {
C++;
random_shuffle(rand.begin(), rand.end());
bool flag = true, tf = false;
for (int j = 0; j < G.size() && flag; j++) {
if (arr[tmp[rand[j]]] == ans[0]) tf = true;
int cnt = 0;
for (int k = 0; k < G.size(); k++) {
int val = arr[tmp[rand[j]]] ^ arr[tmp[rand[k]]];
if (res[res.size()-1] >= val && *lower_bound(res.begin(), res.end(), val) == val)
cnt++;
}
if (cnt < G.size()) flag = false;
}
flag &= tf;
if (flag) {
tmp.clear();
for (int j = 0; j < G.size(); j++)
tmp.pb(rand[j]);
break;
}
if (C > 1000) break;
}
for (int j = 0; j < n; j++) pos[j] += (1<<i);
for (int j : tmp) pos[j] -= (1<<i);
}
for (int i = 0; i < n; i++)
ans[pos[i]] = arr[i];
return ans;
}
Compilation message
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:29:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i = 0; i < exp.size(); i++, j++)
| ~~^~~~~~~~~~~~
Xoractive.cpp:32:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | while (j < all.size()) nums.insert(all[j++] ^ ans[0]);
| ~~^~~~~~~~~~~~
Xoractive.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if (cnt >= G.size()) nxt.pb(j);
| ~~~~^~~~~~~~~~~
Xoractive.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int j = 0; j < tmp.size(); j++)
| ~~^~~~~~~~~~~~
Xoractive.cpp:67:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int j = 0; j < G.size() && flag; j++) {
| ~~^~~~~~~~~~
Xoractive.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int k = 0; k < G.size(); k++) {
| ~~^~~~~~~~~~
Xoractive.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | if (cnt < G.size()) flag = false;
| ~~~~^~~~~~~~~~
Xoractive.cpp:80:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int j = 0; j < G.size(); j++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
492 KB |
Output is correct |
| 2 |
Correct |
10 ms |
492 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
492 KB |
Output is not correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
