# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1211483 | Marco_Escandon | Xoractive (IZhO19_xoractive) | C++20 | 0 ms | 0 KiB |
#include "xoractive.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
//int ask(int position);
//vector<int> get_pairwise_xor(vector<int> positions);
ll x;
vector<int> guess2(vector<int> temp)
{
vector <int> ans;
vector<ll> t1=get_pairwise_xor(temp);
temp.push_back(1);
vector<ll> t2=get_pairwise_xor(temp);
map<ll,ll> mapa;
for(auto i:t2) mapa[i]++;
for(auto i:t1) mapa[i]--;
mapa[0]--;
for(auto i:mapa)
{
if(i.second>0)
{
ans.push_back(x^i.first);
}
}
return ans;
}
vector<int> guess(int n) {
x=ask(1);
vector<map<ll,ll>> cad(n+1);
map<ll,ll> c;
c[x]++;
for(int j=0; j<9; j++)
{
vector<ll> temp;
for(int i=2; i<=n; i++)
if((i&(1<<j))) temp.push_back(i);
if(temp.size()==0) continue;
temp=guess2(temp);
for(auto i:temp) {c[i]++;}
for(int i=2; i<=n; i++)
{
if((i&(1<<j)))
{
for(auto k:temp)
{
cad[i][k]++;
}
}
}
}
cad[1][x]=1;
vector<ll> ans;
for(int i=1; i<=n; i++)
{
for(auto j:cad[i])
{
if(j.second==c[j.first]&&j.second==__builtin_popcount(i))
{
ans.push_back(j.first);
break;
}
}
}
return ans;
}