Submission #259853

#	Time	Username	Problem	Language	Result	Execution time	Memory
259853		Osama_Alkhodairy	Xoractive (IZhO19_xoractive)	C++17	90 / 100	4 ms	512 KiB

Xoractive

#include <bits/stdc++.h>
#include "interactive.h"
//~ #include "grader.cpp"
using namespace std;

vector <int> get(vector <int> &c){
    if(c.size() == 0) return {};
    auto d = get_pairwise_xor(c);
    reverse(d.begin(), d.end());
    while(d.size() && d.back() == 0){
        d.pop_back();
    }
    vector <int> ret;
    for(int i = 1 ; i < (int)d.size() ; i += 2){
        ret.push_back(d[i]);
    }
    reverse(ret.begin(), ret.end());
    return ret;
}
vector <int> intersect(vector <int> a, vector <int> b){
    vector <int> ret;
    while(a.size() && b.size()){
        if(a.back() == b.back()){
            ret.push_back(a.back());
            a.pop_back();
            b.pop_back();
        }
        else if(a.back() > b.back()){
            a.pop_back();
        }
        else{
            b.pop_back();
        }
    }
    reverse(ret.begin(), ret.end());
    return ret;
}
vector <int> del(vector <int> a, vector <int> b){
    vector <int> ret;
    while(a.size()){
        if(b.size()){
            if(b.back() > a.back()){
                b.pop_back();
                continue;
            }
            else if(b.back() == a.back()){
                a.pop_back();
                b.pop_back();
                continue;
            }
        }
        ret.push_back(a.back());
        a.pop_back();
    }
    reverse(ret.begin(), ret.end());
    return ret;
}
vector <int> guess(int n) {
    vector <int> ans(n + 1);
    int p = 0;
    while((1 << (p + 1)) <= n){
        p++;
    }
    ans[(1 << p) - 1] = ask((1 << p) - 1);
    ans[1 << p] = ask(1 << p);
    vector <vector <int> > f(10);
    for(int i = 0 ; i <= p ; i++){
        vector <int> all;
        for(int j = 1 ; j <= n ; j++){
            if((j >> i) & 1) all.push_back(j);
        }
        int m = i == p ? (1 << p) : (1 << p) - 1;
        auto g = get(all);
        all.erase(find(all.begin(), all.end(), m));
        auto h = get(all);
        f[i] = del(g, h);
        f[i].push_back(0);
        for(auto &j : f[i]) j ^= ans[m];
    }
    vector <int> all;
    for(int i = 0 ; i < 10 ; i++){
        sort(f[i].begin(), f[i].end());
        for(auto &j : f[i]){
            all.push_back(j);
        }
    }
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    for(int i = 1 ; i <= n ; i++){
        vector <int> cands = all;
        for(int j = 0 ; j < 10 ; j++){
            if((i >> j) & 1){
                cands = intersect(cands, f[j]);
            }
            else{
                cands = del(cands, f[j]);
            }
        }
        ans[i] = cands[0];
    }
    ans.erase(ans.begin());
    return ans;
}

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