Submission #503472

#TimeUsernameProblemLanguageResultExecution timeMemory
503472GurbanXoractive (IZhO19_xoractive)C++17
6 / 100
1 ms328 KiB
#include "bits/stdc++.h" #include "interactive.h" using namespace std; const int maxn=105; int a[maxn]; int lft[maxn],rgt[maxn]; set<int>arr[2*maxn]; vector<int>fn; map<int,vector<int>>m; void f(int l,int r,int nd,int lev){ lft[nd] = l; rgt[nd] = r; m[lev].push_back(nd); if(l == r){ fn.push_back(nd); return; } int md = (l + r) / 2; f(l,md,nd*2,lev+1); f(md+1,r,nd*2+1,lev+1); } set<int>A(vector<int>v){ if(v.empty()) return set<int>(); // for(auto i : v) cout<<i<<' '; // cout<<" ----> "; vector<int>now = v; now.push_back(1); vector<int>nw = get_pairwise_xor(now); vector<int>z = get_pairwise_xor(v); // for(auto i : nw) cout<<i<<' '; // cout<<" ----> "; // for(auto i : z) cout<<i<<' '; // cout<<" ----> "; multiset<int>SS(nw.begin(),nw.end()); for(auto i : z) SS.erase(SS.find(i)); // for(auto i : SS) cout<<i<<' '; // cout<<" ---> "; set<int>jg; for(auto i : SS) jg.insert(i ^ a[1]); jg.erase(a[1]); // for(auto i : jg) cout<<i<<' '; // cout<<'\n'; return jg; } vector<int> guess(int n) { a[1] = ask(1); f(2,n,1,1); vector<int>go; for(int i = 2;i <= n;i++) go.push_back(i); arr[1] = A(go); for(auto i : m){ if(i.first == 1) continue; vector<int>now; for(auto j : i.second){ if(!(j & 1)) for(int k = lft[j];k <= rgt[j];k++){ now.push_back(k); } } set<int>sw = A(now); for(auto j : i.second){ if(j & 1){ arr[j] = arr[(j-1)/2]; for(auto l : arr[j-1]) arr[j].erase(l); } else { for(auto l : arr[j/2]) if(sw.find(l) != sw.end()) arr[j].insert(l); } } } // for(int i = 1;i <= 2*n;i++){ // cout<<i<<' '<<lft[i]<<' '<<rgt[i]<<" ----> "; // for(auto j : arr[i]) cout<<j<<' '; // cout<<'\n'; // } vector<int>ans; ans.push_back(a[1]); for(auto i : fn){ if(!arr[i].empty()) ans.push_back(*arr[i].begin()); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...