#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pp pop_back
#define all(x) (x).begin(), (x).end()
using namespace std;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
cerr<<h;
if(sizeof...(t)){cerr<<", ";debug(t...);}
}
template<typename T>
void debug(vector<T> V){
cerr<<"{";
for(int i=0; i<V.size(); i++){
debug(V[i]);
if(i+1!=V.size())cerr<<", ";
}
cerr<<"}";
}
#define deb(x...) cerr<<#x<<" = ";debug(x);cerr<<"\n";
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
using vvi = vector<vi>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#include "monster.h"
map<pii, bool> M;
bool czy(int a, int b){//T[a]>T[b]
int ans=0;
if(a>b)ans^=1, swap(a, b);
if(M.find(mp(a, b))==M.end()){
M[{a, b}]=Query(a, b);
}
return ans^M[{a, b}];
}
vvi solve(vi V){
if(V.size()==1)return {{V[0]}};
vi L, R;
for(int i=0; i<V.size(); i++){
if(i&1)L.pb(V[i]);
else R.pb(V[i]);
}
vvi l=solve(L);
vvi r=solve(R);
vvi res;
while(l.size() || r.size()){
if(!r.size())res.pb(l.back()), l.pp();
else if(!l.size())res.pb(r.back()), r.pp();
else{
if(l.back().size()==3){
bool b=czy(l.back()[0], r.back()[0]);
if(b!=czy(l.back()[1], r.back()[0])){
b=czy(l.back()[2], r.back()[0]);
}
//deb(b);
if(b)res.pb(l.back()), l.pp();
else{
if(res.size()>=2 && res.back().size()==1 && res[res.size()-2].size()==1){
if(!czy(res[res.size()-2][0], r.back()[0])){
r.back().pb(res[res.size()-2][0]);
r.back().pb(res.back()[0]);
res.pp();
res.pp();
}
}
res.pb(r.back()), r.pp();
}
}
else if(r.back().size()==3){
bool b=czy(r.back()[0], l.back()[0]);
if(b!=czy(r.back()[1], l.back()[0])){
b=czy(r.back()[2], l.back()[0]);
}
if(b)res.pb(r.back()), r.pp();
else{
if(res.size()>=2 && res.back().size()==1 && res[res.size()-2].size()==1){
if(!czy(res[res.size()-2][0], l.back()[0])){
l.back().pb(res[res.size()-2][0]);
l.back().pb(res.back()[0]);
res.pp();
res.pp();
}
}
res.pb(l.back()), l.pp();
}
}
else{
if(czy(l.back()[0], r.back()[0])){
if(r.size()>=2 && czy(r[r.size()-2][0], l.back()[0])){
vi V2;
V2.pb(l.back()[0]);
l.pp();
V2.pb(r.back()[0]);
r.pp();
V2.pb(r.back()[0]);
r.pp();
r.pb(V2);
//deb(l);
//deb(r);
}
else{
res.pb(l.back());
l.pp();
}
}
else{
if(l.size()>=2 && czy(l[l.size()-2][0], r.back()[0])){
vi V2;
V2.pb(r.back()[0]);
r.pp();
V2.pb(l.back()[0]);
l.pp();
V2.pb(l.back()[0]);
l.pp();
l.pb(V2);
//deb(l);
//deb(r);
}
else{
res.pb(r.back());
r.pp();
}
}
}
}
}
reverse(all(res));
deb(V);
deb(res);
return res;
}
vi Solve(int n) {
vi VV;
for(int i=0; i<n; i++)VV.pb(i);
vvi V=solve(VV);
int lst=-1;
deb(V);
for(int i=0; i<V.size(); i++){
if(V[i].size()==3)lst=i;
if(lst==i-2 && czy(V[i][0], V[i-1][0])){
swap(V[i], V[i-1]);
lst=i;
}
}
deb(V);
for(int i=1; i<V.size(); i++){
//deb(i+1);
bool b=0;
for(int j=V[i-1].size()-1; j>=0; j--){
for(int k=0; k<V[i].size(); k++){
//deb(i);
if(!czy(V[i][k], V[i-1][j])){
//deb(k, j, i);
while(j!=V[i-1].size()-1){
swap(V[i-1][2], V[i-1][1]);
swap(V[i-1][1], V[i-1][0]);
j++;
}
while(k!=0 && k!=3){
swap(V[i][2], V[i][1]);
swap(V[i][1], V[i][0]);
k++;
}
//deb(V);
//deb(k, j, i);
b=1;
}
if(b)break;
}
if(b)break;
}
}
deb(V);
vi res(n);
int wsk=0;
for(vi v:V){
for(int i:v){
res[i]=wsk++;
}
}
return res;
}
Compilation message
monster.cpp: In function 'vvi solve(vi)':
monster.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
monster.cpp: In function 'vi Solve(int)':
monster.cpp:151:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
monster.cpp:159:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for(int i=1; i<V.size(); i++){
| ~^~~~~~~~~
monster.cpp:163:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for(int k=0; k<V[i].size(); k++){
| ~^~~~~~~~~~~~
monster.cpp:167:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | while(j!=V[i-1].size()-1){
| ~^~~~~~~~~~~~~~~~~
monster.cpp: In instantiation of 'void debug(std::vector<_Tp>) [with T = int]':
monster.cpp:140:5: required from here
monster.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
monster.cpp:24:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | if(i+1!=V.size())cerr<<", ";
| ~~~^~~~~~~~~~
monster.cpp: In instantiation of 'void debug(std::vector<_Tp>) [with T = std::vector<int>]':
monster.cpp:141:5: required from here
monster.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
monster.cpp:24:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | if(i+1!=V.size())cerr<<", ";
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
304 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
1 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 KB |
Output is correct |
| 7 |
Correct |
1 ms |
208 KB |
Output is correct |
| 8 |
Correct |
1 ms |
208 KB |
Output is correct |
| 9 |
Correct |
1 ms |
208 KB |
Output is correct |
| 10 |
Correct |
1 ms |
208 KB |
Output is correct |
| 11 |
Correct |
1 ms |
208 KB |
Output is correct |
| 12 |
Correct |
1 ms |
208 KB |
Output is correct |
| 13 |
Correct |
1 ms |
208 KB |
Output is correct |
| 14 |
Correct |
1 ms |
208 KB |
Output is correct |
| 15 |
Correct |
1 ms |
208 KB |
Output is correct |
| 16 |
Incorrect |
40 ms |
440 KB |
Wrong Answer [3] |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
304 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
1 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 KB |
Output is correct |
| 7 |
Correct |
1 ms |
208 KB |
Output is correct |
| 8 |
Correct |
1 ms |
208 KB |
Output is correct |
| 9 |
Correct |
1 ms |
208 KB |
Output is correct |
| 10 |
Correct |
1 ms |
208 KB |
Output is correct |
| 11 |
Correct |
1 ms |
208 KB |
Output is correct |
| 12 |
Correct |
1 ms |
208 KB |
Output is correct |
| 13 |
Correct |
1 ms |
208 KB |
Output is correct |
| 14 |
Correct |
1 ms |
208 KB |
Output is correct |
| 15 |
Correct |
1 ms |
208 KB |
Output is correct |
| 16 |
Incorrect |
40 ms |
440 KB |
Wrong Answer [3] |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
230 ms |
1348 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
