#include "monster.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
namespace {
const int N = 1024;
map<pii,int> mp;
bool cmp(int i, int j)
{
assert(i != j);
if (i < j) {
int &x = mp[pii(i, j)];
if (!x)
x = !Query(i, j)+1;
return x-1;
} else {
swap(i, j);
int &x = mp[pii(i, j)];
if (!x)
x = !Query(i, j)+1;
return 2-x;
}
}
vector<int> merge(vector<int> a, vector<int> b) {
vector<int> ans;
int p0 = 0, p1 = 0;
while (p0 < a.size() || p1 < b.size()) {
if (p1 == b.size() || (p0 != a.size() && cmp(a[p0], b[p1])))
ans.push_back(a[p0++]);
else
ans.push_back(b[p1++]);
}
return ans;
}
vector<int> chain[N];
struct chain_cmp {
bool operator()(const vector<int> *a, const vector<int> *b) const {
return a->size() > b->size();
}
};
vector<int> get_chain(int n)
{
priority_queue<vector<int> *, vector<vector<int> *>, chain_cmp> pq;
Loop (i,0,n) {
chain[i] = {i};
pq.push(chain+i);
}
while (pq.size() > 1) {
auto a = pq.top(); pq.pop();
auto b = pq.top(); pq.pop();
*a = merge(*a, *b);
pq.push(a);
}
return *pq.top();
}
vector<int> mysolve(vector<int> vec)
{
if (vec.size() == 1)
return vec;
if (vec.size() == 2)
return {vec[1], vec[0]};
assert(vec.size() != 3);
int n = vec.size();
vector<int> ans;
int p0 = 0, p1 = 0;
if (cmp(vec[0], vec[2]) && cmp(vec[1], vec[3])) {
ans.push_back(vec[1]);
ans.push_back(vec[0]);
p0 = p1 = 2;
} else if (cmp(vec[0], vec[2]) && !cmp(vec[1], vec[3])) {
ans.push_back(vec[0]);
p0 = p1 = 1;
} else {
if (vec.size() != 6) {
auto tmp = mysolve(vector<int>(vec.begin()+3, vec.end()));
if (!cmp(vec[0], tmp[0]))
ans = {vec[2], vec[1], vec[0]};
else if (!cmp(vec[1], tmp[0]))
ans = {vec[0], vec[2], vec[1]};
else
ans = {vec[1], vec[0], vec[2]};
ans.insert(ans.end(), tmp.begin(), tmp.end());
return ans;
}
int lst = -1, fst = -1;
Loop (i,0,3) Loop (j,3,6) {
if (!cmp(vec[i], vec[j])) {
lst = vec[i];
fst = vec[j];
break;
}
}
vector<int> v1, v2;
v1 = {vec[0], vec[1], vec[2]};
v2 = {vec[3], vec[4], vec[5]};
while (v1.back() != lst) {
int x = v1.back();
v1.pop_back();
v1.insert(v1.begin(), x);
}
while (v2.front() != fst) {
int x = v2.back();
v2.pop_back();
v2.insert(v1.begin(), x);
}
ans = v1;
ans.insert(ans.end(), v2.begin(), v2.end());
return ans;
}
while (p0 < n) {
while (p1 < n-1) {
if (!cmp(ans.back(), vec[p1]))
break;
++p1;
}
LoopR (i,p0,p1+1)
ans.push_back(vec[i]);
p0 = p1 = p1+1;
}
return ans;
}
} // namespace
std::vector<int> Solve(int n) {
vector<int> vec = get_chain(n);
vector<int> ans = mysolve(vec);
vector<int> fans(n);
Loop (i,0,n)
fans[ans[i]] = i;
return fans;
}
Compilation message
monster.cpp: In function 'std::vector<int> {anonymous}::merge(std::vector<int>, std::vector<int>)':
monster.cpp:34:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while (p0 < a.size() || p1 < b.size()) {
| ~~~^~~~~~~~~~
monster.cpp:34:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while (p0 < a.size() || p1 < b.size()) {
| ~~~^~~~~~~~~~
monster.cpp:35:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | if (p1 == b.size() || (p0 != a.size() && cmp(a[p0], b[p1])))
| ~~~^~~~~~~~~~~
monster.cpp:35:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | if (p1 == b.size() || (p0 != a.size() && cmp(a[p0], b[p1])))
| ~~~^~~~~~~~~~~
monster.cpp: In function 'std::vector<int> {anonymous}::get_chain(int)':
monster.cpp:54:15: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
54 | chain[i] = {i};
| ^
monster.cpp:54:15: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
| # |
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 |
Correct |
0 ms |
208 KB |
Output is correct |
| 8 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 9 |
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 |
Correct |
0 ms |
208 KB |
Output is correct |
| 8 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
908 KB |
Output is correct |
| 2 |
Correct |
81 ms |
884 KB |
Output is correct |
| 3 |
Correct |
53 ms |
964 KB |
Output is correct |
| 4 |
Correct |
88 ms |
964 KB |
Output is correct |
| 5 |
Correct |
78 ms |
936 KB |
Output is correct |
| 6 |
Correct |
52 ms |
892 KB |
Output is correct |
| 7 |
Correct |
51 ms |
856 KB |
Output is correct |
| 8 |
Correct |
66 ms |
956 KB |
Output is correct |
| 9 |
Incorrect |
59 ms |
944 KB |
Wrong Answer [3] |
| 10 |
Halted |
0 ms |
0 KB |
- |
