#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]);
}
if(b)res.pb(l.back()), l.pp();
else 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 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();
l.pb(V2);
}
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);
}
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;
for(int i=0; i<V.size(); i++){
if(V[i].size()==3)lst=i;
if(lst==i-2){
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(n);
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:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
monster.cpp: In function 'vi Solve(int)':
monster.cpp:124:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
monster.cpp:132:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for(int i=1; i<V.size(); i++){
| ~^~~~~~~~~
monster.cpp:136:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int k=0; k<V[i].size(); k++){
| ~^~~~~~~~~~~~
monster.cpp:140:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | while(j!=V[i-1].size()-1){
| ~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
208 KB |
Wrong Answer [3] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
208 KB |
Wrong Answer [3] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
155 ms |
1172 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
