#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include "interactive.h"
using namespace std;
map <int, int> mp;/*
vector <int> a;
int n;
int ask(int position) {
return a[position - 1];
}
vector<int> get_pairwise_xor(vector<int> positions) {
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;
}*/
vector <int> guess(int n)
{
vector <int> v;
v.resize(n);
v[0] = ask(1);
for (int i = 0; (1 << i) <= n; i++)
{
vector <int> poz;
vector <int> poz1;
vector <int> poz2;
int cnt = 0, n1, n2;
for (int j = 2; j <= n; j++)
if (j & (1 << i))
poz.push_back(j), cnt++;
poz1 = get_pairwise_xor(poz);
poz1.resize(cnt * cnt);
n1 = cnt * cnt;
poz.push_back(1);
poz2 = get_pairwise_xor(poz);
n2 = (cnt + 1) * (cnt + 1);
poz2.resize(n2);
int i1 = 0, i2 = 0;
while (poz1[i1] == 0)
i1++;
while (poz2[i2] == 0)
i2++;
while (i2 < n2 && i1 < n1)
{
if (poz1[i1] == poz2[i2])
i1++, i2++;
if (poz1[i1] > poz2[i2])
{
if (!(mp[poz2[i2] ^ v[0]] & (1 << i)))
mp[poz2[i2] ^ v[0]] += (1 << i);
i2++;
}
}
while (i2 < n2)
{
if (!(mp[poz2[i2] ^ v[0]] & (1 << i)))
mp[poz2[i2] ^ v[0]] += (1 << i);
i2++;
}
}
for (auto x : mp)
v[x.second - 1] = x.first;
return v;
}/*
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
a.push_back(x);
}
a.resize(n);
vector<int> participant_solution = guess(n);
participant_solution.resize(n);
for (int i = 0; i < n; i++)
cout << participant_solution[i] << " ";
return 0;
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
1 ms |
200 KB |
Output is correct |
4 |
Correct |
1 ms |
200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
328 KB |
Output is not correct |
2 |
Halted |
0 ms |
0 KB |
- |