#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];
bool chain_cmp(vector<int> *a, vector<int> *b) { return a->size() > b->size(); }
vector<int> get_chain(int n)
{
priority_queue<vector<int> *> 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();
}
} // namespace
std::vector<int> Solve(int n) {
vector<int> vec = get_chain(n);
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 {
int cnt = 0;
vector<int> dard;
Loop (i,1,n) {
if (!cmp(vec[0], vec[i]))
dard.push_back(i);
if (dard.size() == 2)
break;
}
if (dard.size() == 1) {
ans.push_back(vec[0]);
ans.push_back(vec[2]);
ans.push_back(vec[1]);
p0 = p1 = 3;
} else {
p0 = 0, p1 = 2;
while (p1 < n-1) {
if (!cmp(vec[p1+1], vec[1]))
break;
++p1;
}
LoopR (i,0,p1+1)
ans.push_back(vec[i]);
p0 = p1 = p1+1;
}
}
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;
}
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:50:15: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
50 | chain[i] = {i};
| ^
monster.cpp:50:15: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:76:7: warning: unused variable 'cnt' [-Wunused-variable]
76 | int cnt = 0;
| ^~~
monster.cpp: At global scope:
monster.cpp:44:6: warning: 'bool {anonymous}::chain_cmp(std::vector<int>*, std::vector<int>*)' defined but not used [-Wunused-function]
44 | bool chain_cmp(vector<int> *a, vector<int> *b) { return a->size() > b->size(); }
| ^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
316 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 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
0 ms |
208 KB |
Output is correct |
| 10 |
Correct |
1 ms |
256 KB |
Output is correct |
| 11 |
Correct |
0 ms |
208 KB |
Output is correct |
| 12 |
Correct |
1 ms |
208 KB |
Output is correct |
| 13 |
Correct |
0 ms |
208 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
208 KB |
Wrong Answer [3] |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
316 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 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
0 ms |
208 KB |
Output is correct |
| 10 |
Correct |
1 ms |
256 KB |
Output is correct |
| 11 |
Correct |
0 ms |
208 KB |
Output is correct |
| 12 |
Correct |
1 ms |
208 KB |
Output is correct |
| 13 |
Correct |
0 ms |
208 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
208 KB |
Wrong Answer [3] |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
204 ms |
1848 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
