#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
bool check(vector<pair<int, int>> &v1, vector<pair<int, int>> &v2, vector<pair<int, int>> &v3, int d){
return max(d, (v3.empty() ? 0 : v3.back().first)) >= max((v1.empty() ? 0 : v1.back().first), (v2.empty() ? 0 : v2.back().first));
}
void combine(vector<pair<int, int>> &v1, vector<pair<int, int>> &v2, vector<pair<int, int>> &v3, int &last, int d){
if(v3.size() == 0) return;
if(v1.size() + v2.size() <= v3.size() && (last == 3 || check(v1, v2, v3, d))){
for(auto p : v2)
v1.push_back(p);
sort(v1.begin(), v1.end());
swap(v2, v3);
v3.clear();
if(last == 2)
last = 1;
else if(last == 3)
last = 2;
} else if(v1.size() + v3.size() <= v2.size() && (last == 2 || check(v1, v3, v2, d))){
for(auto p : v3)
v1.push_back(p);
sort(v1.begin(), v1.end());
v3.clear();
if(last == 3)
last = 1;
} else if(v2.size() + v3.size() <= v1.size() && (last == 1 || check(v2, v3, v1, d))){
for(auto p : v3)
v2.push_back(p);
sort(v2.begin(), v2.end());
v3.clear();
if(last == 3)
last = 2;
}
}
vector<int> createFunTour(int N, int Q) {
int c = 0;
for(int i = 1; i < N; i++){
int ans = attractionsBehind(c, i);
if(ans*2 > N)
c = i;
}
//cout<<"centroid: "<<c<<"\n";
vector<int> tavC(N), inds;
for(int i = 0; i < N; i++){
tavC[i] = hoursRequired(c, i);
if(tavC[i] == 1)
inds.push_back(i);
}
if(inds.size() < 2)
return {0, 1};
vector<int> tav1(N), tav2(N);
for(int i = 0; i < N; i++)
tav1[i] = hoursRequired(inds[0], i);
for(int i = 0; i < N; i++)
tav2[i] = hoursRequired(inds[1], i);
vector<pair<int, int>> v1, v2, v3;
for(int i = 0; i < N; i++){
if(i == c) continue;
if(tav1[i] < tav2[i] && tav1[i] < tavC[i])
v1.push_back(make_pair(tavC[i], i));
else if(tav2[i] < tav1[i] && tav2[i] < tavC[i])
v2.push_back(make_pair(tavC[i], i));
else
v3.push_back(make_pair(tavC[i], i));
}
if(v1.size() <= v2.size() && v1.size() <= v3.size())
v1.push_back(make_pair(0, c));
else if(v2.size() <= v1.size() && v2.size() <= v3.size())
v2.push_back(make_pair(0, c));
else
v3.push_back(make_pair(0, c));
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
sort(v3.begin(), v3.end());
/*cout<<"csop1\n";
for(auto p : v1)
cout<<p.first<<" "<<p.second<<"\n";
cout<<"csop2\n";
for(auto p : v2)
cout<<p.first<<" "<<p.second<<"\n";
cout<<"csop3\n";
for(auto p : v3)
cout<<p.first<<" "<<p.second<<"\n";*/
int last = 0, d = (int)1e9;
combine(v1, v2, v3, last, d);
if(v3.size() == 0){
last = 2;
if(v2.size() > v1.size())
last = 1;
} else{
last = 1;
if(v2.back().first > v1.back().first)
last = 2;
if(v3.back().first > v2.back().first && v3.back().first > v1.back().first)
last = 3;
last++;
if(last == 4)
last = 1;
}
vector<int> ret;
while(!v1.empty() || !v2.empty() || !v3.empty()){
if(v3.empty()){
if(last == 1){
if(v2.empty()) return ret;
ret.push_back(v2.back().second);
last = 2;
v2.pop_back();
} else{
if(v1.empty()) return ret;
ret.push_back(v1.back().second);
last = 1;
v1.pop_back();
}
} else{
if(last == 1){
if(v2.empty() || v3.empty()) return {};
if(v2.back().first > v3.back().first){
ret.push_back(v2.back().second);
last = 2;
d = v2.back().first;
v2.pop_back();
} else{
ret.push_back(v3.back().second);
last = 3;
d = v3.back().first;
v3.pop_back();
}
} else if(last == 2){
if(v2.empty() || v3.empty()) return {};
if(v1.back().first > v3.back().first){
ret.push_back(v1.back().second);
last = 1;
d = v1.back().first;
v1.pop_back();
} else{
ret.push_back(v3.back().second);
last = 3;
d = v3.back().first;
v3.pop_back();
}
} else{
if(v1.empty() || v2.empty()) return {};
if(v1.back().first > v2.back().first){
ret.push_back(v1.back().second);
last = 1;
d = v1.back().first;
v1.pop_back();
} else{
ret.push_back(v2.back().second);
last = 2;
d = v2.back().first;
v2.pop_back();
}
}
combine(v1, v2, v3, last, d);
}
}
return ret;
}
