Submission #425043

#	Time	Username	Problem	Language	Result	Execution time	Memory
425043		doowey	Xoractive (IZhO19_xoractive)	C++14	100 / 100	128 ms	456 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = 101;
const int B = 7;
vector<int> h1[B];
vector<int> h2[B];

vector<int> xor_sums(vector<int> ff){
    if(ff.empty()) return {};
    vector<int> nw = get_pairwise_xor(ff);
    vector<int> ret;
    int las = -1;
    for(auto x : nw){
        if(x != 0){
            if(x != las){
                ret.push_back(x);
                las = x;
            }
            else{
                las = -1;
            }
        }
    }
    return ret;
}

map<int, int> cnt;

vector<int> guess(int n) {
	int base = ask(1);
    for(int lg = 0; lg < B; lg ++ ){
        vector<int> que;
        for(int i = 2; i <= n; i ++ ){
            if((i & (1 << lg))){
                que.push_back(i);
            }
        }
        h1[lg] = xor_sums(que);
        que.push_back(1);
        h2[lg] = xor_sums(que);
    }
    int maxi;
    vector<int> outp = {base};
    for(int iq = 2 ; iq <= n; iq ++ ){
        map<int, int> cand;
        for(int lg = 0 ;lg < B; lg ++ ){
            cnt.clear();
            for(auto x : h2[lg]){
                cnt[x] ++ ;
            }
            for(auto x : h1[lg]){
                cnt[x] -- ;
            }
            vector<int> has;
            for(auto x : cnt){
                if(x.se == 1)
                    has.push_back(((x.fi)^base));
            }
            if((iq & (1 << lg))){
                for(auto x : has){
                    cand[x] ++ ;
                }
            }
            else{
                for(auto x : has){
                    cand[x] = -(int)1e9;
                }
            }
        }
        maxi = 0;
        for(auto x : cand){
            if(x.se > maxi){
                maxi = x.se;
            }
        }
        for(auto x : cand){
            if(x.se == maxi) {
                outp.push_back(x.fi);
                break;
            }
        }
    }
	return outp;
}

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