Submission #441591

#	Time	Username	Problem	Language	Result	Execution time	Memory
441591		leaked	Xoractive (IZhO19_xoractive)	C++14	6 / 100	6 ms	584 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>
#define vec vector
#define pb push_back
#define f first
#define s second
#define sz(x) (int)x.size()
using namespace std;
vec<int> get(int f,vec<int> inds){
    for(auto &z : inds) z+=2;
    vec<int>lol;
    map<int,int>mp;
    vec<int>a=inds,b=inds;
    b.pb(1);
    a=get_pairwise_xor(a),b=get_pairwise_xor(b);
    vec<int>c;
    for(auto &z : a) mp[z]--;
    for(auto &z : b) mp[z]++;
    mp[0]--;
    for(auto &z : mp){
        int x=z.s;
        x/=2;
        while(x--){
            c.pb(z.f);
        }
    }
//    cout<<sz(c)<<endl;
//    cerr<<
//    cerr<<"LOL"<<endl;
    for(auto &z : c){
//        cerr<<z<<' ';
        z=(z^f);
//        cerr<<z<<' ';
    }
//    cerr<<endl;
    sort(c.begin(),c.end());
    return c;
}
vec<int>vls;
map<int,int>w[1000];
vec<int>asked[1000];
bool used[1001];
int answ[1001];
int st=-1;
int to=-1;
void rec(int l,int r,int lvl){
    vec<int>vc;
    for(int i=l;i<=r;i+=lvl){
        vc.pb(i);
    }
//    if(lvl==1)
    asked[lvl]=vc;
    vec<int>wl=get(st,vc);
    for(auto &z : wl) w[lvl][z]++;
    if(lvl==1) vls=wl;
    to=lvl;
    if(l+lvl>r) return;
    rec(l,r,lvl*2);
}
vector<int> guess(int n) {
	vector <int> ans;
    st=ask(1);
    rec(0,n-2,1);
//    vls=w[1];
    for(int t=to;t>=1;t/=2){
        for(auto &i : asked[t]){
            if(used[i]) continue;
            for(auto &x : vls){
                int ok=1;
                for(int p=1;p<=to;p*=2){
                    if(i%p){
                        ok&=(w[p][x]==0);
                    }
                    else{
                        ok&=(w[p][x]>0);
                    }
                }
                if(ok){
                    for(int p=1;p<=to;p*=2){
                        if(i%p==0){
                            w[p][x]--;
                        }
                    }
                    answ[i]=x;
                    used[i]=1;
                    break;
                }
            }
            assert(used[i]);
        }
    }
    ans.pb(st);
    for(int i=0;i<n-1;i++){
        ans.pb(answ[i]);
    }
	return ans;
}

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