#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> Solve(int n)
{
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
function<void(int, int)> solve = [&](int l, int r)
{
if (l == r - 1)
{
return;
}
int mid = (l + r) / 2;
solve(l, mid);
solve(mid, r);
int i = l, j = mid;
vector<int> res;
while (i < mid && j < r)
{
if (!Query(ord[i], ord[j]))
{
res.push_back(ord[i]);
i++;
}
else
{
res.push_back(ord[j]);
j++;
}
}
while (i < mid)
{
res.push_back(ord[i]);
i++;
}
while (j < r)
{
res.push_back(ord[j]);
j++;
}
for (int k = l; k < r; k++)
{
ord[k] = res[k - l];
}
};
solve(0, n);
auto get = [&]() -> int
{
if (!Query(ord[0], ord[2]))
{
int j = 3;
while (j < n && !Query(ord[0], ord[j]))
{
j++;
}
if (Query(ord[1], ord[j]))
{
reverse(ord.begin() + 1, ord.begin() + j + 1);
}
else
{
swap(ord[0], ord[1]);
reverse(ord.begin() + 2, ord.begin() + j + 1);
}
return j + 1;
}
if (Query(ord[0], ord[3]))
{
if (Query(ord[1], ord[3]))
{
int j = 4;
while (j < n && Query(ord[1], ord[j]))
{
j++;
}
reverse(ord.begin(), ord.begin() + j);
return j;
}
else
{
swap(ord[0], ord[2]);
return 4;
}
}
if (n == 4)
{
swap(ord[1], ord[2]);
return 4;
}
if (n == 5)
{
if (Query(ord[0], ord[4]))
{
swap(ord[0], ord[2]);
}
else
{
swap(ord[1], ord[2]);
}
swap(ord[3], ord[4]);
return 5;
}
if (n == 6)
{
if (Query(ord[1], ord[5]))
{
swap(ord[1], ord[2]);
swap(ord[3], ord[5]);
}
else if (Query(ord[1], ord[3]))
{
swap(ord[1], ord[2]);
swap(ord[4], ord[5]);
}
else if (Query(ord[0], ord[5]))
{
swap(ord[0], ord[2]);
swap(ord[3], ord[5]);
}
else
{
swap(ord[0], ord[2]);
swap(ord[4], ord[5]);
}
return 6;
}
if (!Query(ord[3], ord[5]))
{
int j = 6;
while (j < n && !Query(ord[3], ord[j]))
{
j++;
}
if (Query(ord[4], ord[j]))
{
reverse(ord.begin() + 4, ord.begin() + j + 1);
}
else
{
swap(ord[3], ord[4]);
reverse(ord.begin() + 5, ord.begin() + j + 1);
}
if (Query(ord[0], ord[3]))
{
swap(ord[0], ord[2]);
}
else
{
swap(ord[1], ord[2]);
}
return j + 1;
}
if (Query(ord[3], ord[6]))
{
if (Query(ord[4], ord[6]))
{
int j = 7;
while (j < n && Query(ord[4], ord[j]))
{
j++;
}
reverse(ord.begin() + 3, ord.begin() + j);
if (Query(ord[0], ord[3]))
{
swap(ord[0], ord[2]);
}
else
{
swap(ord[1], ord[2]);
}
return j;
}
else
{
swap(ord[3], ord[5]);
if (Query(ord[0], ord[3]))
{
swap(ord[0], ord[2]);
}
else
{
swap(ord[1], ord[2]);
}
return 7;
}
}
if (Query(ord[1], ord[5]))
{
swap(ord[1], ord[2]);
swap(ord[3], ord[5]);
}
else if (Query(ord[1], ord[3]))
{
swap(ord[1], ord[2]);
swap(ord[4], ord[5]);
}
else if (Query(ord[0], ord[5]))
{
swap(ord[0], ord[2]);
swap(ord[3], ord[5]);
}
else
{
swap(ord[0], ord[2]);
swap(ord[4], ord[5]);
}
return 6;
};
int i = get();
while (i < n)
{
int j = i;
while (j < n && !Query(ord[i - 1], ord[j]))
{
j++;
}
reverse(ord.begin() + i, ord.begin() + j + 1);
i = j + 1;
}
vector<int> ans(n);
for (int i = 0; i < n; i++)
{
ans[ord[i]] = i;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [3] |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [3] |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
592 KB |
Output is correct |
| 2 |
Incorrect |
40 ms |
600 KB |
Wrong Answer [3] |
| 3 |
Halted |
0 ms |
0 KB |
- |
