Submission #1105198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105198		denislav	Xoractive (IZhO19_xoractive)	C++17	100 / 100	6 ms	592 KiB

Xoractive

# include <iostream>
# include <vector>
# include <set>
# include <map>
# include <algorithm>
# include "interactive.h"
//# include "grader.cpp"
using namespace std;

vector<int> xors(int k, vector<int> v)
{
    vector<int> del=get_pairwise_xor(v);

    v.insert(v.begin(),k);
    v=get_pairwise_xor(v);

    multiset<int> s;
    for(int x: v) s.insert(x);
    for(int x: del) s.erase(s.find(x));
    s.erase(0);

    vector<int> ans;
    map<int, bool> vis;
    for(int x: s)
    {
        if(vis[x]==0)
        {
            ans.push_back(x);
            vis[x]=1;
        }
    }

    return ans;
}

vector<int> guess(int n)
{

    vector<int> ans(n);
    ans[0]=ask(1);
    map<int, int> mapi;
    for(int bit=0;bit<=6;bit++)
    {
        vector<int> v;
        for(int i=2;i<=n;i++) if((i&(1<<bit))>0) v.push_back(i);
        if((int)v.size()==0) continue;

        //cout<<"bit:"<<bit<<"\n";
        //for(int x: v) cout<<x<<" ";
        //cout<<"\n";

        v=xors(1,v);
        for(int x: v)
        {
            mapi[x]+=(1<<bit);
            //cout<<"->"<<x<<endl;
        }
    }

    for(pair<int, int> p: mapi)
    {
        ans[p.second-1]=(p.first^ans[0]);
    }

	return ans;
}

/*
5
1 2 3 4 5
*/

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