# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
505151 | 2022-01-10T19:16:27 Z | rainliofficial | Xoractive (IZhO19_xoractive) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "interactive.h" #include "grader.cpp" using namespace std; #define ll long long #define pii pair<int, int> #define f first #define s second multiset<int> filter(vector<int>& all, vector<int>& exclude){ multiset<int> allValues; for (int i : all){ allValues.insert(i); } for (int i : exclude){ if (allValues.find(i) != allValues.end()){ allValues.erase(allValues.find(i)); } } return allValues; } vector<int> guess(int n) { vector<int> ans(n); vector<int> allPositions(n); for (int i=0; i<n; i++){ allPositions[i] = i+1; } vector<int> exludeFirst(n-1); for (int i=1; i<n; i++){ exludeFirst[i-1] = i+1; } int first = ask(1); vector<int> allPairwiseXor = get_pairwise_xor(allPositions); vector<int> excludeFirstXor = get_pairwise_xor(exludeFirst); multiset<int> allValues = filter(allPairwiseXor, excludeFirstXor); vector<int> valToInd(n+1); // Maps an element to its answer index valToInd[first] = 1; // Look at answer indexes by bit int maxBits = log2(n)+1; for (int i=0; i<=maxBits; i++){ vector<int> currSet; // The set of numbers with this bit ON for (int j=2; j<=n; j++){ if (j & (1<<i)){ // This bit is ON currSet.push_back(j); } } if (currSet.empty()){ continue; } vector<int> currSetXor = get_pairwise_xor(currSet); currSet.push_back(1); vector<int> xorWithFirst = get_pairwise_xor(currSet); multiset<int> currSetResult = filter(xorWithFirst, currSetXor); set<int> processed; for (int curr : currSetResult){ if (curr == 0 || processed.find(curr) != processed.end()){ continue; } processed.insert(curr); int val = curr ^ first; // Convert XOR value to orig value valToInd[val] += 1<<i; } } for (int i=1; i<=n; i++){ ans[valToInd[i]-1] = i; } return ans; }