Submission #1211199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211199		a.pendov	Xoractive (IZhO19_xoractive)	C++20	100 / 100	3 ms	664 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>
using namespace std;
unordered_multiset<int> s;
unordered_set<int> s1[8];

long long solve(int a)
{
    int x;
    for(int i=0;i<7;i++)
    {
        if(!(a&(1LL<<i)))
        {
            x=i;
            break;
        }
    }
    //cout<<"   "<<a<<" "<<x<<endl;
    for(auto i:s1[x])
    {
        int br=0;
        for(int j=0;j<7;j++)
        {
            if(a&(1LL<<j))
            {
                if(s1[j].find(i)==s1[j].end())br++;
            }
            else
            {
                if(s1[j].find(i)!=s1[j].end())br++;
            }
        }
        if(br==7)return i;
    }

    return -1;
}

vector<int> guess(int n)
{
    int x=ask(n);
    vector<int> v;
    vector<int> ans;
    for(int i=0;i<7;i++)
    {
        v.clear();
        s.clear();
        for(int j=0;j<n-1;j++)
        {
            if(!(j&(1LL<<i)))
            {
                v.push_back(j+1);
            }
        }
        if(v.size()==0)continue;
        ans=get_pairwise_xor(v);
        for(auto h:ans)s.insert(h);
        v.push_back(n);
        ans=get_pairwise_xor(v);
        for(auto h:ans)
        {
            if(s.find(h)==s.end())
            {
                s1[i].insert(h);
            }
            else
            {
                s.erase(s.find(h));
            }
        }
        s1[i].erase(0);
        //cout<<i<<"     ";
        //for(auto h:s1[i])cout<<(h^x)<<" ";
        //cout<<endl;
    }
    ans.clear();
    for(int i=0;i<n-1;i++)
    {
        ans.push_back(solve(i)^x);
    }

    ans.push_back(x);

    return ans;
}

• Subtask 1: 6 / 6
• Subtask 2: 94 / 94