Submission #382419

#	Time	Username	Problem	Language	Result	Execution time	Memory
382419		BartolM	Xoractive (IZhO19_xoractive)	C++17	88 / 100	6 ms	640 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 lo[2*OFF], hi[2*OFF];
set <int> br[2*OFF];
vector <int> sol;

void rek(int pos, int a, int b) {
    lo[pos]=a; hi[pos]=b;
    if (pos<off) {
        rek(pos*2, a, (a+b)/2);
        rek(pos*2+1, (a+b)/2, b);
    }
}

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<svi.size()) ret.insert(svi[i++]);

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

    return ret;
}

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

	while (off<(n+1)) off*=2;

	rek(1, 0, off);

	vector <int> v;
	for (int i=2; i<=n; ++i) v.pb(i);
	br[1]=pitaj(v);

	for (int i=1; (1<<i)<=off; ++i) {
	    v.clear();
	    for (int node=(1<<i); node<(1<<(i+1)); node+=2) {
	        for (int j=lo[node]; j<hi[node]; ++j) if (j>1 && j<=n) v.pb(j);
	    }
	    set <int> MS=pitaj(v);
	    for (int lef=(1<<i); lef<(1<<(i+1)); lef+=2) {
            int par=lef/2, rig=lef+1;
            for (int x:br[par]) {
                if (MS.count(x)) br[lef].insert(x);
                else br[rig].insert(x);
            }
	    }
	}
	sol.pb(jed);
    #if DEBUG
        printf("%d ", jed);
    #endif // DEBUG
	for (int i=2; i<=n; ++i) {
        assert((int)br[i+off].size()==1);
        int x=*br[i+off].begin();
        sol.pb(jed^x);
//        printf("%d ", jed^x);
	}
//	printf("\n")
	return sol;
}

Compilation message (stderr)

Xoractive.cpp: In function 'std::set<int> pitaj(std::vector<int>)':
Xoractive.cpp:59:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     while (i<svi.size()) ret.insert(svi[i++]);
      |            ~^~~~~~~~~~~

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