Submission #1168789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168789		kh0i	Xoractive (IZhO19_xoractive)	C++20	100 / 100	3 ms	512 KiB

Xoractive

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#include "interactive.h"
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

#ifdef LOCAL
int n, a[103];
vector<int> p;
int que;
void init(){
    n = get_rand(2, 100);
    p.resize(1 << 10);
    iota(all(p), 0);
    shuffle(all(p), rng);
    for(int i = 1; i <= n; ++i)
        a[i] = p[i - 1];
    cout << n << endl;
    for(int i = 1; i <= n; ++i)
        cout << a[i] << " \n"[i == n];
    que = 0;
}
int ask(int i){
    ++que;
    return a[i];
}
vector<int> get_pairwise_xor(vector<int> idx){
    ++que;
    vector<int> res;
    for(int i : idx)
        for(int j : idx)
            res.push_back(a[i] ^ a[j]);
    sort(all(res));
    return res;
}
void check(vector<int> res){
    for(int i = 0; i < n; ++i){
        if(res[i] != a[i + 1]){
            cout << "wrong" << endl;
            exit(-1);
        }
    }
    cout << "ok, que = " << que << endl;
}
#endif

vector<int> guess(int n){
    vector<int> a(n);
    a[0] = ask(1);
    map<int, int> res;
    for(int i = 0; (1 << i) <= n; ++i){
        vector<int> idx;
        for(int j = 2; j <= n; ++j)
            if((j >> i) & 1)
                idx.push_back(j);
        vector<int> fi = get_pairwise_xor(idx);
        idx.push_back(1);
        vector<int> se = get_pairwise_xor(idx);
        map<int, int> cnt;
        for(int x : se)
            ++cnt[x];
        for(int x : fi)
            --cnt[x];
        for(auto p : cnt)
            if(p.S > 0 and p.F)
                res[p.F ^ a[0]] |= (1 << i);
    }
    for(auto p : res)
        a[p.S - 1] = p.F;
    return a;
}

#ifdef LOCAL
int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    for(int iter = 1; iter <= 10000; ++iter){
        init();
        check(guess(n));
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}
#endif

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