Submission #431372

#	Time	Username	Problem	Language	Result	Execution time	Memory
431372		Runtime_error_	Xoractive (IZhO19_xoractive)	C++14	0 / 100	6 ms	456 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 n,valn;
vector<int> numbers[inf],ans[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?valn:0));
        else
            s.erase(s.find(o));
    }
    for(auto o:sret)
        ret.pb(o);

    return ret;
}


vector<int> GetValues(vector<int> query){
    vector<int> v1,v2;

    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) {
    vector<int> ret;
    n = N;
    valn = ask(n);
    for(int bit = 0;bit<7;bit++){
        for(int i=1;i<n;i++)
            if((1<<bit) & i)
                numbers[bit].pb(i);
        if(!numbers[bit].empty())
            ans[bit] = GetValues(numbers[bit]);
    }

    for(int i=1;i<n;i++){
        vector<int> candidate;
        for(int bit = 0;bit<7;bit++){
            if(!((1<<bit) & i))
                continue;
            if(candidate.empty())
                candidate = ans[bit];
            else{
                vector<int> new_candidate;
                for(auto o:ans[bit])
                    if(count(begin(candidate),end(candidate),o))
                        new_candidate.pb(o);
                candidate = new_candidate;
            }
        }
        for(int bit = 0;bit<7;bit++){
            if((1<<bit) &i)
                continue;
            for(auto o:numbers[bit])
                if(count(begin(candidate),end(candidate),o))
                    candidate.erase(find(begin(candidate),end(candidate),o));
        }
        ret.pb(candidate[0]);
    }
    ret.pb(valn);
    return ret;
}
/*
4
1 5 3 6
*/

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