#include "longesttrip.h"
#include <vector>
#include <stack>
#include <iostream>
#include <deque>
#include <queue>
using namespace std;
vector<int> longest_trip(int N, int D)
{
deque<int> flink;
deque<int> slink;
flink.push_back(0);
queue<int> to_link;
for (int i = 1; i < N; i++) {
to_link.push(i);
}
for (; !to_link.empty(); to_link.pop()) {
bool add_next = are_connected({flink.back()}, {to_link.front()});
if (add_next) {
flink.push_back(to_link.front());
} else {
slink.push_back(to_link.front());
to_link.pop();
break;
}
}
for (; !to_link.empty(); to_link.pop()) {
bool in_flink = are_connected({flink.back()}, {to_link.front()});
if (in_flink) {
flink.push_back(to_link.front());
if (slink.empty()) continue;
if (are_connected({flink.back()}, {slink.back()})) {
while (!slink.empty()) {
flink.push_back(slink.back());
slink.pop_back();
}
}
} else {
slink.push_back(to_link.front());
}
}
vector<int> fLink;
for (; !flink.empty(); flink.pop_back()) {
fLink.push_back(flink.back());
}
vector<int> sLink;
for (; !slink.empty(); slink.pop_back()) {
sLink.push_back(slink.back());
}
if (sLink.size() < 1) {
return fLink;
} else if (fLink.size() < 1) {
return sLink;
}
// cout << "///log\n";
if (fLink.size() < sLink.size()) swap(sLink,fLink);
if (are_connected({fLink[0]}, {sLink[0]})) {
reverse(sLink.begin(), sLink.end());
sLink.insert(sLink.end(), fLink.begin(), fLink.end());
return sLink;
} else if (are_connected({fLink[0]}, {sLink.back()})) {
sLink.insert(sLink.end(), fLink.begin(), fLink.end());
return sLink;
}
if (are_connected({fLink.back()}, {sLink[0]})) {
fLink.insert(fLink.end(), sLink.begin(), sLink.end());
return fLink;
} else if (are_connected({fLink.back()}, {sLink.back()})) {
reverse(fLink.begin(), fLink.end());
sLink.insert(sLink.end(), fLink.begin(), fLink.end());
return sLink;
}
// for (int x : fLink) {
// cout << x << " ";
// }
// cout << endl;
//
// for (int x : sLink) {
// cout << x << " ";
// }
// cout << endl;
bool same_component = are_connected(fLink, sLink);
// cout << "///log\n";
if (!same_component) {
if (fLink.size() > sLink.size()) {
return fLink;
} else {
return sLink;
}
}
int l = 0, r = fLink.size() - 1;
// cout << "///log\n";
while (l < r) {
int mid = (l+r)/2;
vector<int> testV;
for (int i = l; i <= mid; i++) {
testV.push_back(fLink[i]);
}
if (are_connected(testV, sLink)) {
r = mid;
} else {
l = mid+1;
}
}
int connectionPoint = fLink[r];
int connectionIndex = r;
// cout << connectionPoint << "\n";
// vector<int> ans;
// for (int i = 0; i < fLink.size(); i++) {
// if (i == connectionIndex) continue;
// ans.push_back(fLink[i]);
// }
//
// ans.push_back(connectionPoint);
// if (are_connected({connectionPoint}, {sLink.front()})) {
// for (int i = 0; i < sLink.size(); i++) {
// ans.push_back(sLink[i]);
// }
// } else {
// for (int i = sLink.size()-1; i >= 0; i--) {
// ans.push_back(sLink[i]);
// }
// }
// cout << "///log\n";
// for (auto x : ans) {
// cout << x << " ";
// }
// cout << "\n////logend\n";
// return ans;
l = 0, r = sLink.size() - 1;
while (l < r) {
int mid = (l+r)/2;
vector<int> testV;
for (int i = l; i <= mid; i++) {
testV.push_back(sLink[i]);
}
if (are_connected({connectionPoint}, testV)) {
r = mid;
} else {
l = mid+1;
}
}
int cP2 = sLink[r];
vector<int> ans;
for (int i = connectionIndex+1; i < fLink.size(); i++) {
ans.push_back(fLink[i]);
}
for (int i = 0; i < connectionIndex; i++) {
ans.push_back(fLink[i]);
}
ans.push_back(connectionPoint);
ans.push_back(cP2);
for (int i = r+1; i < sLink.size(); i++) {
ans.push_back(sLink[i]);
}
for (int i = 0; i < r; i++) {
ans.push_back(sLink[i]);
}
return ans;
}
