Submission #241798

#	Time	Username	Problem	Language	Result	Execution time	Memory
241798		valerikk	Xoractive (IZhO19_xoractive)	C++17	6 / 100	5 ms	436 KiB

Xoractive

#include "interactive.h"
#include<set>
#include<map>
#include<cassert>

using namespace std;

#define mp make_pair
#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
typedef long long ll;

vector<int> get_xor(vector<int> a) {
    vector<int> b;
    for (auto x : a) b.pb(x + 1);
    auto q = get_pairwise_xor(b);
    map<int, int> ma;
    for (auto x : q) {
        if (x != 0) ma[x]++;
    }
    vector<int> w;
    for (auto x : ma) {
        assert(x.y % 2 == 0);
        while (x.y > 0) {
            w.pb(x.x);
            x.y -= 2;
        }
    }
    return w;
}

vector<int> get_se(int a0, vector<int> b) {
    auto c = b;
    c.pb(0);
    auto vb = get_xor(b), vc = get_xor(c);
    map<int, int> ma;
    for (auto x : vc) ma[x]++;
    for (auto x : vb) ma[x]--;
    vector<int> d;
    for (auto x : ma) {
        while (x.y--) d.pb(x.x ^ a0);
    }
    return d;
}

vector<int> guess(int n) {
    vector<int> a;
    for (int i = 1; i <= n; i++) a.pb(ask(i));
    return a;
}
/*
vector<int> guess(int n) {
    vector<int> a(n);
    a[0] = ask(1);
    vector<int> b;
    for (int i = 1; i < n; i++) b.pb(i);
    vector<pair<pair<int, int>, vector<int>>> now{{{1, n - 1}, get_se(a[0], b)}};
    while (!now.empty()) {
        vector<int> gg;
        for (auto x : now) {
            if (x.x.x == x.x.y) a[x.x.x] = x.y[0]; else {
                int mi = (x.x.x + x.x.y) / 2;
                for (int i = mi + 1; i <= x.x.y; i++) gg.pb(i);
            }
        }
        auto v = get_se(a[0], gg);
        set<int> se;
        for (auto x : v) se.insert(x);
        vector<pair<pair<int, int>, vector<int>>> go;
        for (auto x : now) {
            if (x.x.x < x.x.y) {
                int mi = (x.x.x + x.x.y) / 2;
                vector<int> le, ri;
                for (auto y : x.y) {
                    if (se.count(y)) ri.pb(y); else le.pb(y);
                }
                go.pb(mp(mp(x.x.x, mi), le));
                go.pb(mp(mp(mi + 1, x.x.y), ri));
            }
        }
        now = go;
    }
    return a;
}
*/

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