Submission #382509

#	Time	Username	Problem	Language	Result	Execution time	Memory
382509		BartolM	Xoractive (IZhO19_xoractive)	C++17	100 / 100	5 ms	512 KiB

Xoractive

#include <bits/stdc++.h>
#include "interactive.h"

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int OFF=128;
const int N=105;

int n, off=1;
int jed;
int sol[N];

set <int> pitaj(vector <int> v) {
    set <int> ret;

//    printf("pitam za: ");
//    for (int x:v) printf("%d ", x);
//    printf("\n");

    if (v.empty()) return ret;
    vector <int> izbaci=get_pairwise_xor(v);
    v.pb(1);
    vector <int> svi=get_pairwise_xor(v);

//    printf("izbaci: ");
//    for (int x:izbaci) printf("%d ", x);
//    printf("\nsvi: ");
//    for (int x:svi) printf("%d ", x);
//    printf("\n");

    svi.erase(svi.begin());

    int i=0;
    for (int x:izbaci) {
        while (svi[i]<x) ret.insert(svi[i++]);
        i++;
    }
    while (i<(int)svi.size()) ret.insert(svi[i++]);

//    for (int x:ret) printf("%d ", x);
//    printf("\n");

    return ret;
}

void impera(vector <vector <int> > pos, vector <vector <int> > br) {
    if (pos.empty()) return;
//    printf("---------------------------\n");

    vector <int> que;
    vector <vector <int> > np, nbr;
    int ind=-1;
    for (vector <int> v:pos) {
        ind++;

//        printf("ind: %d, pos: ", ind);
//        for (int x:v) printf("%d ", x);
//        printf(", br: ");
//        for (int x:br[ind]) printf("%d ", x);
//        printf("\n");

        if ((int)v.size()==1 && br[ind].size()) {
            sol[v[0]]=br[ind][0];
            continue;
        }

        vector <int> p_l, p_r;
        int siz=v.size();
        for (int i=0; i<(int)v.size()/2+siz%2; ++i) que.pb(v[i]), p_l.pb(v[i]);
        for (int i=(int)v.size()/2+siz%2; i<(int)v.size(); ++i) p_r.pb(v[i]);
        np.pb(p_l);
        if (p_r.size()) np.pb(p_r);
    }
    set <int> S=pitaj(que);
    for (vector <int> v:br) {
        if (v.size()==1) continue;
        vector <int> br_l, br_r;

        if (v.empty()) {
            for (int x:S) br_l.pb(x);
        }
        else {
            for (int x:v) {
                if (S.count(x)) br_l.pb(x), S.erase(x);
                else br_r.pb(x);
            }
        }
        nbr.pb(br_l); nbr.pb(br_r);
    }
    impera(np, nbr);
}

vector<int> guess(int nn) {
    n=nn;
    jed=ask(1);

    vector <vector <int> > pos0, br0;
    vector <int> pom;
    pos0.pb(pom); br0.pb(pom);
    for (int i=2; i<=n; ++i) pos0[0].pb(i);

    impera(pos0, br0);

    vector <int> res;
    res.pb(jed);
    for (int i=2; i<=n; ++i) res.pb(sol[i]^jed);
    return res;
}

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