// M
#include<bits/stdc++.h>
#include "interactive.h"
using namespace std;
vector < int > RP;
mt19937 Rnd(time(0));
inline int Ask(int i)
{
return (ask(RP[i]));
}
inline vector < int > GetSet(vector < int > A)
{
for (int &a : A)
a = RP[a];
vector < int > Rs = get_pairwise_xor(A);
/*printf("A is : ");
for (int a : A)
printf("%d ", a);
printf("\n");
printf("Rs is : ");
for (int a : Rs)
printf("%d ", a);
printf("\n");*/
for (int i = 0; i < (int)A.size(); i ++)
assert(Rs[0] == 0), Rs.erase(Rs.begin());
vector < int > Rs2;
for (int i = 0; i < (int)Rs.size(); i += 2)
Rs2.push_back(Rs[i]);
/*printf("Rs2 is : ");
for (int a : Rs2)
printf("%d ", a);
printf("\n");*/
assert((int)Rs2.size() == (int)A.size() * ((int)A.size() - 1) / 2);
return Rs2;
}
const int LG = 7;
set < int > All[LG];
multiset < int > ST[LG];
vector < int > vec[LG];
vector < int > guess(int n)
{
RP.resize(n);
iota(RP.begin(), RP.end(), 1);
shuffle(RP.begin(), RP.end(), Rnd);
int lg = LG;
while ((1 << lg) >= n)
lg --;
lg ++;
vector < int > Res(n, -1);
Res[0] = Ask(0);
for (int j = 0; j < lg; j ++)
Res[1 << j] = Ask(1 << j);
for (int j = 0; j < lg; j ++)
{
vec[j].clear();
vec[j].push_back(0);
for (int i = 1; i < n; i ++)
if (i >> j & 1)
vec[j].push_back(i);
vec[j] = GetSet(vec[j]);
ST[j].clear();
for (int a : vec[j])
ST[j].insert(a);
ST[j].erase(ST[j].lower_bound(Res[0] ^ Res[1 << j]));
for (int a : ST[j])
if (ST[j].count(a ^ Res[0] ^ Res[1 << j]))
All[j].insert(a ^ Res[0]);
}
auto Try = [&](int i)
{
bool hs = 0;
set < int > Nw;
for (int j = 0; j < lg; j ++)
if (i >> j & 1)
{
if (hs == 0)
{
hs = 1;
for (int a : All[j])
Nw.insert(a);
continue;
}
set < int > Tobe;
for (int a : Nw)
if (All[j].count(a))
Tobe.insert(a);
Nw.swap(Tobe);
Tobe.clear();
}
assert(Nw.size());
if (Nw.size() > 1)
return 0;
Res[i] = * Nw.begin();
return 1;
};
auto Del = [&](int i)
{
for (int j = 0; j < lg; j ++)
if (i >> j & 1)
{
for (int h = 0; h < n; h ++)
if (i != h && Res[h] != -1 && (h == 0 || (h >> j & 1)))
ST[j].erase(ST[j].lower_bound(Res[i] ^ Res[h]));
All[j].clear();
for (int a : ST[j])
if (ST[j].count(a ^ Res[0] ^ Res[1 << j]))
All[j].insert(a ^ Res[0]);
}
return ;
};
while (true)
{
bool Fail = 1;
for (int i = 0; i < n; i ++)
if (Res[i] == -1 && Try(i))
Fail = 0, Del(i);
if (Fail) break;
}
for (int i = 0; i < n; i ++)
assert(Res[i] != -1);
vector < int > Rs(n);
for (int i = 0; i < n; i ++)
Rs[RP[i] - 1] = Res[i];
return Rs;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
0 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
768 KB |
Output is correct |
| 2 |
Correct |
27 ms |
768 KB |
Output is correct |
| 3 |
Runtime error |
10 ms |
1280 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
