Submission #566346

#	Time	Username	Problem	Language	Result	Execution time	Memory
566346		Stickfish	Xoractive (IZhO19_xoractive)	C++17	100 / 100	6 ms	464 KiB

Xoractive

#include "interactive.h"
#include <map>
using namespace std;
 
map<int, int> ra;
 
map<int, int> ask_compr(vector<int> pos) {
    vector<int> ansv = get_pairwise_xor(pos);
    map<int, int> ansmp;
    for (auto x : ansv)
        ++ansmp[x];
    return ansmp;
}
 
void get_bit(int n, int bt) {
    vector<int> pos;
    for (int i = 1; i <= n; ++i) {
        if (i & bt)
            pos.push_back(i);
    }
    map<int, int> mp0 = ask_compr(pos);
    pos.push_back(n + 1);
    map<int, int> mp1 = ask_compr(pos);
    for (auto [x, cnt] : mp1) {
        if (cnt > mp0[x]) {
            ra[x] += bt;
        }
    }
}
 
vector<int> guess(int n) {
    vector<int> ans(n);
    ans[n - 1] = ask(n);
    for (int bt = 1; bt + 1 < n; bt *= 2) {
        get_bit(n - 1, bt);
    }
    for (auto [avl, i] : ra)
        ans[i - 1] = avl ^ ans[n - 1];
    return ans;
}

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