#include "monster.h"
#include <algorithm>
#include <vector>
using namespace std;
#define sz(x) ((int)(x).size())
bool stg(int n, int i)
{
int q = 0;
for (int j = 0; j < n; ++j)
{
if (i == j)
continue;
if (Query(i, j))
++q;
}
return (q == 1);
}
void ezr(int n, vector<int>& v, int i, int j)
{
if (i == 0)
{
for (int k = i; k <= j; ++k)
{
if (!stg(n, v[k]))
{
for (int t = k + 1; t <= j; ++t)
swap(v[t], v[t - 1]);
break;
}
}
if (Query(v[2], v[1]))
swap(v[0], v[1]);
}
else
{
for (int k = i; k <= j; ++k)
{
if (Query(v[k], v[i - 1]))
{
for (int t = k - 1; t >= j; --t)
swap(v[t], v[t + 1]);
break;
}
}
if (Query(v[1], v[0]))
swap(v[1], v[2]);
}
}
vector<int> Solve(int n)
{
vector<int> v;
v.push_back(0);
for (int i = 1; i < n; ++i)
{
int l = 0, r = sz(v) - 1;
int u = -1;
while (l <= r)
{
int m = (l + r) / 2;
if (Query(i, v[m]))
{
u = m;
l = m + 1;
}
else
r = m - 1;
}
vector<int> nv;
if (u == -1)
nv.push_back(i);
for (int j = 0; j < sz(v); ++j)
{
nv.push_back(v[j]);
if (u == j)
nv.push_back(i);
}
v = nv;
}
for (int i = 0; i < n - 1; ++i)
{
if (i + 1 == n - 1)
{
if (!Query(v[i], v[i + 1]))
swap(v[i], v[i + 1]);
}
else
{
if (Query(v[i], v[i + 2]))
{
int j = i + 2;
while (j + 1 < n && Query(v[i], v[j + 1]))
++j;
if ((j - i + 1) == 3)
{
ezr(n, v, i, j);
i = j;
continue;
}
int ty = 1;
if (i == 0)
{
if (stg(n, v[j]))
ty = 0;
}
else
{
if (!Query(v.back(), i - 1))
ty = 0;
}
if (ty == 0)
reverse(v.begin() + i, v.begin() + j + 1);
else
reverse(v.begin() + i, v.begin() + j);
i = j;
}
else
{
int j = i + 2;
while (j + 1 < n && !Query(v[i], v[j + 1]))
++j;
++j;
if ((j - i + 1) == 3)
{
ezr(n, v, i, j);
i = j;
continue;
}
int ty = 1;
if (i == 0)
{
if (stg(n, v[j]))
ty = 0;
}
else
{
if (!Query(v[0], i - 1))
ty = 0;
}
if (ty == 0)
reverse(v.begin() + i + 1, v.begin() + j + 1);
else
{
swap(v[0], v[1]);
reverse(v.begin() + i + 2, v.begin() + j + 1);
}
i = j;
}
}
}
vector<int> ans(n);
for (int i = 0; i < n; ++i)
ans[v[i]] = i;
return ans;
}
/*
5
1 2 3 4 0
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
0 ms |
208 KB |
Output is correct |
| 4 |
Correct |
0 ms |
208 KB |
Output is correct |
| 5 |
Correct |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
0 ms |
208 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
208 KB |
Wrong Answer [3] |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
0 ms |
208 KB |
Output is correct |
| 4 |
Correct |
0 ms |
208 KB |
Output is correct |
| 5 |
Correct |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
0 ms |
208 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
208 KB |
Wrong Answer [3] |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
460 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
