Submission #868710

#	Time	Username	Problem	Language	Result	Execution time	Memory
868710		alexdd	Xoractive (IZhO19_xoractive)	C++17	88 / 100	5 ms	1112 KiB

Xoractive

#include "interactive.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> ans;
int cate,maxd;
int le[405];
int ri[405];
int niv[405];
vector<int> aux[20];
vector<int> rez[20];
map<int,int> tori[20];
void divide_init(int st, int dr, int depth, int nod)
{
    cate=max(cate,nod);
    maxd=max(maxd,depth);
    le[nod]=st;
    ri[nod]=dr;
    niv[nod]=depth;
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    divide_init(st,mij,depth+1,nod*2);
    divide_init(mij+1,dr,depth+1,nod*2+1);
}
void divide_final(int nod, vector<int> vals)
{
    /*cout<<nod<<"   "<<le[nod]<<" "<<ri[nod]<<": ";
    for(auto x:vals)
        cout<<x<<" ";
    cout<<"\n";*/
    if(le[nod]==ri[nod])
    {
        ans[le[nod]-1] = vals[0]^ans[0];
        return;
    }
    vector<int> vals_le;
    vector<int> vals_ri;
    for(auto x:vals)
    {
        if(tori[niv[nod]+1][x]>0)
            vals_ri.push_back(x);
        else
            vals_le.push_back(x);
    }
    divide_final(nod*2,vals_le);
    divide_final(nod*2+1,vals_ri);
}
vector<int> guess(int n)
{
    ans.resize(n);
	ans[0]=ask(1);
	cate=1;
	maxd=0;
    divide_init(2,n,1,1);
    for(int i=1;i<=cate;i++)
    {
        if(i%2==1)
        {
            for(int j=le[i];j<=ri[i];j++)
                aux[niv[i]].push_back(j);
        }
    }
    vector<int> cv0;
    vector<int> cv1;
    for(int i=1;i<=maxd;i++)
    {
        cv0 = get_pairwise_xor(aux[i]);
        for(auto x:cv0)
            tori[i][x]--;
        aux[i].push_back(1);
        cv1 = get_pairwise_xor(aux[i]);
        for(auto x:cv1)
            tori[i][x]++;
        rez[i].clear();
        for(auto it:tori[i])
            for(int j=0;j<it.second/2;j++)
                rez[i].push_back(it.first);
    }
    divide_final(1,rez[1]);
	return ans;
}

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