| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1348715 | michael12 | Xoractive (IZhO19_xoractive) | C++20 | 0 ms | 0 KiB |
// #include "interactive.h"
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<numeric>
#include<string>
#include<stack>
#include<queue>
#include<string.h>
#include<array>
#include<climits>
#include<algorithm>
#include<cmath>
using namespace std;
#define ff first
#define ss second
const int mx = 1500000;
#define int long long
const long long inf = 1e18;
#define endl '\n'
namespace {
const int MAX_VALUE_OF_N = 100;
const int MAX_VALUE_OF_Q = 200;
int numberOfQueries = 0;
int n;
std::vector<int> a;
void wrong_answer(const char *MSG) {
printf("-1\n");
exit(0);
}
}
void query() {
numberOfQueries++;
if (numberOfQueries > MAX_VALUE_OF_Q) {
wrong_answer("Number of queries exceeded");
}
}
int ask(int position) {
query();
if (position < 1 || position > n) {
wrong_answer("Not correct position");
}
return a[position - 1];
}
vector<int> get_pairwise_xor(vector<int> positions) {
query();
if (positions.empty() || positions.size() > n) {
wrong_answer("Not correct size");
}
sort(positions.begin(), positions.end());
for (int i = 1; i < positions.size(); i++) {
if (positions[i] == positions[i - 1]) {
wrong_answer("Not unique");
}
}
for (int i = 0; i < positions.size(); i++) {
if (positions[i] < 1 || positions[i] > n) {
wrong_answer("Not correct position");
}
}
vector<int> pairwise_xor;
for (int i = 0; i < positions.size(); i++) {
for (int j = 0; j < positions.size(); j++) {
pairwise_xor.push_back(a[positions[i] - 1] ^ a[positions[j] - 1]);
}
}
sort(pairwise_xor.begin(), pairwise_xor.end());
return pairwise_xor;
}
vector<int> guess(int n){
vector<int> T(n);
T[0] = ask(1);
map<int, int> mp1;
for(int i = 0; (1 << i) <= 7; i++){
vector<int> g;
for(int j = 2; j <= n; j++){
if(j & (1 << i)){
g.push_back(j);
}
}
if(g.empty()) continue;
map<int, int> mp;
vector<int> A = get_pairwise_xor(g);
g.push_back(1);
vector<int> B = get_pairwise_xor(g);
for(auto t : B){
mp[t] += 1;
}
for(auto t : A){
mp[t] -= 1;
}
for(auto h : mp){
if(h.ss){
mp1[h.ff ^ T[0]] += (1 << i);
}
}
}
for(auto d : mp1){
T[d.ss - 1] = d.ff;
}
return T;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
vector<int> t = guess(n);
for(auto v : t){
cout << v << " ";
}
}