This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "interactive.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int q(int x){
return ask(x+1);
}
vector<int> q(vector<int> v){
if(v.empty())
return {};
for(auto &u : v)
u++;
vector<int> res = get_pairwise_xor(v);
reverse(all(res));
for(int i = 0; i < v.size(); ++i)
res.pop_back();
reverse(all(res));
return res;
}
map<int, int> mpp[109];
vector<int> guess(int n) {
int maxbit = 0;
while(++maxbit)
if((1<<maxbit) > n-1)
break;
vector<int> ans(n, -1);
vector<int> known;
for(int i = 0; i < n; ++i)
if((1<<maxbit)-1-i < n){
known.pb(i);
known.pb((1<<maxbit)-1-i);
break;
}
for(auto u : known)
ans[u] = q(u);
for(int bit = 0; bit < maxbit; ++bit)
for(int col = 0; col < 2; ++col){
vector<int> vec;
for(int i = 0; i < n; ++i){
if(((i&(1<<bit)) > 0) == col)
vec.pb(i);
}
//cout << bit << ' ' << col << ' ' << vec.size() << '\n';
vec = q(vec);
for(auto val : known)
if(((val&(1<<bit)) > 0) == col)
for(auto &u : vec)
u ^= ans[val];
for(int i = 0; i < n; ++i)
if(((i&(1<<bit)) > 0) == col)
for(auto u : vec)
mpp[i][u]++;
}
for(int i = 0; i < n; ++i){
if(ans[i] != -1) continue;
pii maxi = {-1, -1};
for(auto u : mpp[i]){
maxi = max(maxi, {u.ss, u.ff});
//cout << i << ' ' << u.ff << ' ' << u.ss << '\n';
}
ans[i] = maxi.ss;
/*for(int j = i+1; j < n; ++j){
int common = 0;
for(int bit = 0; bit < maxbit; ++bit)
common += ((i&(1<<bit)) == (j&(1<<bit)));
mpp[j][ans[i]] -= common;
}*/
}
//for(auto u : ans)
// cout << u << '\n';
return ans;
}
Compilation message (stderr)
Xoractive.cpp: In function 'std::vector<int> q(std::vector<int>)':
Xoractive.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int i = 0; i < v.size(); ++i)
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |