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 "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 solve6 = [&]()
{
for (int i = 0; i < 3; i++)
{
for (int j = 3; j < 6; j++)
{
if (Query(ord[i], ord[j]))
{
swap(ord[2], ord[i]);
swap(ord[3], ord[j]);
goto found;
}
}
}
found:
if (Query(ord[0], ord[2]))
{
swap(ord[0], ord[1]);
}
if (Query(ord[3], ord[5]))
{
swap(ord[4], ord[5]);
}
};
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;
}
}
if (n == 4)
{
if (Query(ord[0], ord[3]))
{
swap(ord[0], ord[2]);
}
else if (Query(ord[1], ord[3]))
{
swap(ord[1], ord[2]);
}
else
{
swap(ord[0], ord[1]);
}
return 4;
}
if (n == 5)
{
swap(ord[3], ord[4]);
if (Query(ord[0], ord[3]))
{
swap(ord[0], ord[2]);
}
else if (Query(ord[1], ord[3]))
{
swap(ord[1], ord[2]);
}
else
{
swap(ord[0], ord[1]);
}
return 5;
}
if (n == 6)
{
solve6();
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;
}
}
solve6();
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |