Submission #635185

#	Time	Username	Problem	Language	Result	Execution time	Memory
635185		Bruteforceman	Xoractive (IZhO19_xoractive)	C++11	100 / 100	6 ms	472 KiB

Xoractive

    #include <bits/stdc++.h>
    #include "interactive.h"
    using namespace std;
     
    vector<int> ans;
    map<int, int> pos;
     
    vector<int> guess(int n) {
    	ans.assign(n, 0);
    	ans[0] = ask(1);
     
    	int logN = 31 - __builtin_clz(n);
    	//cerr << logN << '\n';
    	for (int b = 0; b <= logN; b++) {
    		cerr << b << '\n';
    		// get the values of ans[0] ^ ... for the indices whose b-th bit is on
    		// by inserting 1 to said set of indices
    		multiset<int> bitval;
     
    		vector<int> toQuery, queryAns;
    		for (int i = 2; i <= n; i++) {
    			if (i & (1 << b)) {toQuery.push_back(i);}
    		}
     
    		toQuery.push_back(1);
    		queryAns = get_pairwise_xor(toQuery);
    		for (auto &i : queryAns) {bitval.insert(i);}
     
    		toQuery.pop_back();
    		queryAns = get_pairwise_xor(toQuery);
    		for (auto &i : queryAns) {bitval.erase(bitval.lower_bound(i));}
     
    		//for (auto &i : bitval) {cout << i << ' ';} cout << '\n';
     
    		// remove 0 because all elements are distinct
    		bitval.erase(0);
     
    		for (auto &i : bitval) {
    			pos[i ^ ans[0]] |= (1 << b);
    			//cout << (i ^ ans[0]) << ' ' << b << '\n';
    		}
    	}
     
    	for (auto &[val, idx] : pos) {
    		ans[idx-1] = val;
    	}
    	
    	//for (auto &i : ans) cout << i << ' '; cout << '\n';
    	return ans;
    }
     
    // Grader
    #ifdef Zanite
    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;
    }
     
    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

Compilation message (stderr)

Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:44:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |      for (auto &[val, idx] : pos) {
      |                 ^

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