Submission #420681

#	Time	Username	Problem	Language	Result	Execution time	Memory
420681		Runtime_error_	Xoractive (IZhO19_xoractive)	C++14	88 / 100	14 ms	1256 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>
#define pi pair<int,int>
#define pb push_back
#define mid (l+r)/2
using namespace std;
const int inf = 109;
int ans[inf],n;
vector<int> ValuesInRange[inf][inf];

vector<int> RemoveCommon(vector<int> v1,vector<int> v2,bool IsVals){
    vector<int> ret;
    multiset<int>s;
    set<int> sret;

    for(auto &o:v2){
        if(!IsVals && o == 0)continue;
        s.insert(o);
    }
    for(auto &o:v1){
        if(!IsVals && o == 0)continue;
        if(!s.count(o))
            sret.insert(o^(!IsVals?ans[n]:0));
        else
            s.erase(s.find(o));
    }
    for(auto o:sret)
        ret.pb(o);

    return ret;
}


vector<int> GetValues(vector<pair<int,int> > ranges){
    vector<int> query,v1,v2;
    set<int>s;
    for(auto o:ranges)
        for(int i=o.first;i<=o.second;i++)
            query.pb(i);

    v2 = get_pairwise_xor(query);
    query.pb(n);
    v1 = get_pairwise_xor(query);

    return RemoveCommon(v1,v2,0);
}

queue<pair<int,int> > q;

vector<int> guess(int N) {
    n = N;
    ans[n] = ask(n);
    ValuesInRange[1][n-1] = GetValues({pi(1,n-1)});

    q.push(pi(1,n-1));
    while(!q.empty()){
        vector<pair<int,int> > CurRanges,QueryRanges;
        int sz = q.size();
        while(sz--){
            int l = q.front().first,r = q.front().second;
            q.pop();
            if(l == r)continue;
            CurRanges.pb(pi(l,r));
            QueryRanges.pb(pi(l,mid));
            q.push(pi(l,mid));
            q.push(pi(mid+1,r));
        }
        if(CurRanges.empty())break;
        vector<int> QueryValues = GetValues(QueryRanges);
        for(auto o:CurRanges){
            int l = o.first,r = o.second;
            ValuesInRange[mid+1][r] = RemoveCommon(ValuesInRange[l][r],QueryValues,1);
            ValuesInRange[l][mid] = RemoveCommon(ValuesInRange[l][r],ValuesInRange[mid+1][r],1);
        }
    }
    vector<int> ret;
    for(int i=1;i<n;i++)
        ret.pb(ValuesInRange[i][i][0]);
    ret.pb(ans[n]);
    return ret;
}
/*
4
1 5 3 6
*/

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