#include <bits/stdc++.h>
#include "interactive.h"
#ifdef BLAT
#include "debug/debug.hpp"
#else
#define debug(x...)
#endif
using namespace std;
void remove_junk(vector <int> &v) {
vector <int> v2;
for (int i = 0; i < v.size(); i += 2)
if (v[i] != 0)
v2.push_back(v[i]);
v = v2;
}
int first, offset;
vector <int> ans;
void check(const vector <int> &q, int chosen) {
debug(q, chosen);
vector <int> v, others;
for (int i = 0; i < q.size(); i++) {
if (chosen & (1 << i))
v.push_back(q[i] ^ first);
else others.push_back(q[i]);
}
debug(v, others);
vector <int> pattern;
for (int i = 0; i < v.size(); i++)
for (int j = i + 1; j < v.size(); j++)
pattern.push_back(v[i] ^ v[j]);
sort(pattern.begin(), pattern.end());
debug(pattern);
if (pattern == others)
for (int i = 0; i < v.size(); i++)
ans[offset + i] = v[i] ^ first;
}
void backtrack(const vector <int> &q, int chosen, int pos = 0) {
int n = q.size();
if (pos == n) {
if (__builtin_popcount(chosen) == (n + 1) / 2)
check(q, chosen);
return;
}
if (__builtin_popcount(chosen) < (n + 1) / 2)
backtrack(q, chosen ^ (1 << pos), pos + 1);
backtrack(q, chosen, pos + 1);
}
vector <int> guess(int n) {
vector <int> asks;
ans.resize(n);
ans[0] = first = ask(1);
for (int i = 2; i <= n; i += 7) {
asks.clear(); asks.push_back(1);
for (int j = i; j < i + 7 && j <= n; j++)
asks.push_back(j);
debug(asks);
auto q = get_pairwise_xor(asks);
remove_junk(q);
debug(q);
int chosen = 0;
offset = i - 1;
if (q.size() == asks.size() * (asks.size() - 1) / 2)
backtrack(q, chosen);
/*for (auto it : q)
cerr << it << ' ';
cerr << '\n';*/
}
return ans;
}
Compilation message
Xoractive.cpp: In function 'void remove_junk(std::vector<int>&)':
Xoractive.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for (int i = 0; i < v.size(); i += 2)
| ~~^~~~~~~~~~
Xoractive.cpp: In function 'void check(const std::vector<int>&, int)':
Xoractive.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int i = 0; i < q.size(); i++) {
| ~~^~~~~~~~~~
Xoractive.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
Xoractive.cpp:33:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int j = i + 1; j < v.size(); j++)
| ~~^~~~~~~~~~
Xoractive.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Output is not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3063 ms |
208 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
