제출 #241807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241807		valerikk	Xoractive (IZhO19_xoractive)	C++14	0 / 100	15 ms	768 KiB

Xoractive

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define f first
#define s second
#define pb push_back
#define ins insert

#define trav(a,x) for (auto a:x)
#define F0R(i,a,b) for (int i = (a); i < (b); i++)
#define FOR(i,n) for (int i = 0; i < (n); i++)

#define resz resize
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef pair<pi,vi> T;
/*
vi hid;

int ask(int i) {
    return hid[i - 1];
}

vi getPairwiseXor(vi pos) {
    vi res;
    trav(i,pos) trav(j,pos) res.pb(hid[i-1]^hid[j-1]);
    return res;
}
*/
vi getXor(vi pos) {
    /*cout << "pos: ";
    for (auto it = pos.begin(); it != pos.end(); it++) {
        if (it != pos.begin()) cout << ", ";
        cout << *it;
    }
    cout << '\n';*/
    vi POS;
    trav(x,pos) POS.pb(x+1);
    vi ans = get_pairwise_xor(POS);
    map<int,int> mp;
    trav(x,ans) if (x != 0) mp[x]++;
    vi res;
    trav(x,mp) FOR(_,x.s/2) res.pb(x.f);
    return res;
}

vi getSet(int a0, vi pos) {
    vi POS = pos;
    POS.pb(0);
    vi ans = getXor(pos), ANS = getXor(POS);
    map<int,int> mp;
    trav(x,ans) mp[x]--; trav(x,ANS) mp[x]++;
    vi res;
    trav(x,mp) FOR(i,x.s) res.pb(x.f^a0);
    return res;
}

vi guess(int n) {
    vi a(n);
    a[0] = ask(1);
    vi pos;
    F0R(i,1,n) pos.pb(i);
    vector<T> layer={{{1,n-1},getSet(a[0],pos)}};
    while (sz(layer)) {
        /*cout << "layer: ";
        for (auto it = layer.begin(); it != layer.end(); it++) {
            if (it != layer.begin()) cout << ", ";
            cout << "[" << it->f.f << ", " << it->f.s << "]";
        }
        cout << '\n';*/
        vi POS;
        trav(x,layer) {
            if (x.f.f == x.f.s) a[x.f.f] = x.s[0]; else {
                int mi = (x.f.f+x.f.s)/2;
                F0R(i,x.f.f,mi+1) POS.pb(i);
            }
        }
        /*cout << "POS: ";
        for (auto it = POS.begin(); it != POS.end(); it++) {if (it != POS.begin()) cout << ", "; cout << *it;}
        cout << '\n';*/
        vi ANS = getSet(a[0],POS);
        /*cout << "ANS: ";
        for (auto it = ANS.begin(); it != ANS.end(); it++) {if (it != ANS.begin()) cout << ", "; cout << *it;}
        cout << '\n';*/
        set<int> ans;
        trav(x,ANS) ans.ins(x);
        vector<T> LAYER;
        trav(x,layer) {
            if (x.f.f != x.f.s) {
                int mi = (x.f.f+x.f.s)/2;
                vi lef,rig;
                trav(y,x.s) if (ans.count(y)) lef.pb(y); else rig.pb(y);
                LAYER.pb({{x.f.f, mi}, lef});
                LAYER.pb({{mi+1, x.f.s}, rig});
            }
        }
        layer = LAYER;
    }
    return a;
}
/*
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n = rng()%9+2;
        hid.resz(0);
        set<int> S;
        FOR(i,n) {
            int x = rng()%32;
            while (S.count(x)) x = rng()%32;
            S.ins(x);
            hid.pb(x);
        }
        vi ans = guess(n);
        if (ans != hid) {
            cout << "hid: ";
            for (auto it = hid.begin(); it != hid.end(); it++) {if (it != hid.begin()) cout << ", "; cout << *it;}
            cout << "\nans: ";
            for (auto it = ans.begin(); it != ans.end(); it++) {if (it != ans.begin()) cout << ", "; cout << *it;}
        }
    }
    return 0;
}
*/

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