Submission #173362

#	Time	Username	Problem	Language	Result	Execution time	Memory
173362		Abelyan	Xoractive (IZhO19_xoractive)	C++17	100 / 100	6 ms	508 KiB

Xoractive

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

#ifdef ALEXPC
int ask(int position);
std::vector<int> get_pairwise_xor(std::vector<int> positions);
#endif

map<int,int> qan;

vector<int> guess(int n){
	vector<int> ans(n);
	ans[0]=ask(1);
	FOR(i,7){
		vector<int> tv;
		FORT(j,1,n-1){
			if ((1<<i)&j){
				tv.ad(j+1);
			}
		}
		if (tv.size()==0)continue;
		vector<int> gt=get_pairwise_xor(tv);
		trav(k,gt){
			qan[k^ans[0]]-=(1<<i);
		}
		qan[ans[0]]-=(1<<i);
		tv.ad(1);
		gt=get_pairwise_xor(tv);
		trav(k,gt){
			qan[k^ans[0]]+=(1<<i);
		}
	}
	//cout<<qan[2]<<" "<<qan[4]<<endl;
	trav(tv,qan){
		if (tv.sc==0)continue;
		ans[tv.sc/2]=tv.fr;
		//cerr<<tv.sc<<" "<<tv.fr<<endl;
	}
	return ans;
}

#ifdef ALEXPC
namespace {
    const int MAX_VALUE_OF_N = 100;
    const int MAX_VALUE_OF_Q = 200;
    int numberOfQueries = 0;
    int n;
    std::vector<int> a;

    void wrong_answer(const char *MSG) {
        printf("-1\n");
        exit(0);
    }
}

void query() {
    numberOfQueries++;

    if (numberOfQueries > MAX_VALUE_OF_Q) {
        wrong_answer("Number of queries exceeded");
    }
}

int ask(int position) {
    query();
    
    if (position < 1 || position > n) {
        wrong_answer("Not correct position");
    }
    return a[position - 1];

}
vector<int> get_pairwise_xor(vector<int> positions) {
    query();
    
    if (positions.empty() || positions.size() > n) {
        wrong_answer("Not correct size");
    }
    
    sort(positions.begin(), positions.end());
    
    for (int i = 1; i < positions.size(); i++) {
        if (positions[i] == positions[i - 1]) {
            wrong_answer("Not unique");
        }
    }

    for (int i = 0; i < positions.size(); i++) {
        if (positions[i] < 1 || positions[i] > n) {
            wrong_answer("Not correct position");
        }
    }

    vector<int> pairwise_xor;
    
    for (int i = 0; i < positions.size(); i++) {
        for (int j = 0; j < positions.size(); j++) {
            pairwise_xor.push_back(a[positions[i] - 1] ^ a[positions[j] - 1]);
        }
    }
    sort(pairwise_xor.begin(), pairwise_xor.end());

    return pairwise_xor;
}


vector<int> guess(int n);

int main() {
    assert(scanf("%d", &n) == 1);

    assert(1 <= n && n <= MAX_VALUE_OF_N);
    
    for (int i = 1; i <= n; i++) {
        int x;

        assert(scanf("%d", &x) == 1);
        assert(x >= 0 && x <= 1000 * 1000 * 1000);

        a.push_back(x);
    }
    vector<int> participant_solution = guess(n);

    if (participant_solution.size() != n) {
        wrong_answer("-1");
    }

	printf("%d\n", n);
    
    for (auto i: participant_solution) {
        printf("%d ", i);
    }
    printf("\n");
    printf("%d\n", numberOfQueries);
    return 0;
}
#endif

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