Submission #619014

#TimeUsernameProblemLanguageResultExecution timeMemory
619014ZaniteXoractive (IZhO19_xoractive)C++17
100 / 100
5 ms592 KiB
#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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...