oj.uz

Submission #173362

# Submission time Handle Problem Language Result Execution time Memory
173362 2020-01-03T19:24:04 Z Abelyan Xoractive (IZhO19_xoractive) C++17
100 / 100
 6 ms 508 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #2
94.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 4 ms 248 KB Output is correct
8 Correct 6 ms 504 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 6 ms 508 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 6 ms 504 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 6 ms 504 KB Output is correct
15 Correct 4 ms 248 KB Output is correct
16 Correct 6 ms 504 KB Output is correct
17 Correct 6 ms 504 KB Output is correct
18 Correct 6 ms 504 KB Output is correct
19 Correct 4 ms 296 KB Output is correct
20 Correct 6 ms 504 KB Output is correct
21 Correct 6 ms 504 KB Output is correct
22 Correct 6 ms 504 KB Output is correct
23 Correct 4 ms 248 KB Output is correct
24 Correct 6 ms 504 KB Output is correct
25 Correct 6 ms 504 KB Output is correct
26 Correct 6 ms 504 KB Output is correct
27 Correct 4 ms 248 KB Output is correct
28 Correct 6 ms 504 KB Output is correct
29 Correct 6 ms 504 KB Output is correct
30 Correct 6 ms 504 KB Output is correct
31 Correct 4 ms 248 KB Output is correct
32 Correct 6 ms 504 KB Output is correct
33 Correct 6 ms 504 KB Output is correct
34 Correct 6 ms 504 KB Output is correct
35 Correct 4 ms 248 KB Output is correct
36 Correct 6 ms 504 KB Output is correct
37 Correct 6 ms 504 KB Output is correct
38 Correct 6 ms 504 KB Output is correct
39 Correct 4 ms 248 KB Output is correct
40 Correct 6 ms 504 KB Output is correct
41 Correct 6 ms 504 KB Output is correct
42 Correct 6 ms 504 KB Output is correct
43 Correct 4 ms 376 KB Output is correct
44 Correct 6 ms 504 KB Output is correct
45 Correct 6 ms 504 KB Output is correct
46 Correct 6 ms 504 KB Output is correct
47 Correct 4 ms 376 KB Output is correct
48 Correct 6 ms 504 KB Output is correct
49 Correct 6 ms 504 KB Output is correct
50 Correct 6 ms 504 KB Output is correct
51 Correct 4 ms 376 KB Output is correct
52 Correct 6 ms 504 KB Output is correct
53 Correct 6 ms 504 KB Output is correct
54 Correct 6 ms 504 KB Output is correct
55 Correct 4 ms 380 KB Output is correct
56 Correct 6 ms 504 KB Output is correct
57 Correct 6 ms 504 KB Output is correct
58 Correct 6 ms 504 KB Output is correct
59 Correct 4 ms 248 KB Output is correct
60 Correct 6 ms 504 KB Output is correct
61 Correct 6 ms 504 KB Output is correct
62 Correct 6 ms 504 KB Output is correct
63 Correct 4 ms 376 KB Output is correct
64 Correct 6 ms 504 KB Output is correct
65 Correct 6 ms 504 KB Output is correct
66 Correct 6 ms 504 KB Output is correct
67 Correct 4 ms 376 KB Output is correct
68 Correct 6 ms 504 KB Output is correct
69 Correct 6 ms 504 KB Output is correct
70 Correct 6 ms 504 KB Output is correct
71 Correct 4 ms 252 KB Output is correct
72 Correct 6 ms 504 KB Output is correct
73 Correct 6 ms 504 KB Output is correct
74 Correct 6 ms 508 KB Output is correct
75 Correct 4 ms 252 KB Output is correct
76 Correct 6 ms 504 KB Output is correct
77 Correct 6 ms 504 KB Output is correct
78 Correct 6 ms 504 KB Output is correct
79 Correct 4 ms 376 KB Output is correct
80 Correct 6 ms 504 KB Output is correct
81 Correct 6 ms 504 KB Output is correct
82 Correct 6 ms 504 KB Output is correct
83 Correct 4 ms 248 KB Output is correct
84 Correct 6 ms 504 KB Output is correct
85 Correct 6 ms 504 KB Output is correct
86 Correct 6 ms 504 KB Output is correct
87 Correct 4 ms 248 KB Output is correct
88 Correct 6 ms 504 KB Output is correct
89 Correct 6 ms 424 KB Output is correct
90 Correct 6 ms 504 KB Output is correct
91 Correct 4 ms 376 KB Output is correct
92 Correct 6 ms 504 KB Output is correct
93 Correct 6 ms 504 KB Output is correct
94 Correct 6 ms 504 KB Output is correct
95 Correct 4 ms 360 KB Output is correct
96 Correct 6 ms 504 KB Output is correct
97 Correct 6 ms 504 KB Output is correct
98 Correct 6 ms 504 KB Output is correct
99 Correct 4 ms 376 KB Output is correct
100 Correct 6 ms 504 KB Output is correct