// Que problema lindo. Muito foda jeito e o motivo que tudo só se encaixa na solução pra 100 pontos
#include <bits/stdc++.h>
#include "towns.h"
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MAXN = 0;
int getDistance(int i, int j);
inline bool check(int i, int j, vector<bool>& v, vector<int>& db, int lb, int a){
if(i==j)
return 1;
if(v[i]^v[j])
return 0;
if(v[i])
return 1;
int L = (db[i] + db[j] - getDistance(i,j))>>1;
return min(L,db[a]-L) != lb;
}
int hubDistance(int n, int sub){
int a = 0, b;
vector<int> ds (n,0), db(n,0);
int maxi = -1;
for(int i = 1; i < n; i++){
ds[i] = getDistance(0,i);
if(ds[i] > maxi)
maxi = ds[i], b = i;
}
maxi = ds[b];
db[0] = ds[b];
for(int i = 1; i < n; i++){
if(i==b)
continue;
db[i] = getDistance(b,i);
if(db[i] > maxi)
maxi = db[i], a = i;
}
vector<int> dlca(n,0); // dist(lca(x,0) na arvore enraizada no b, b)
vector<bool> bsub(n,0); // verdadeiro se x está na subarvore do b
int resp = INF;
for(int i = 0; i < n; i++){
dlca[i] = (db[0] + db[i] - ds[i])>>1;
resp = min(resp, max(dlca[i], db[a] - dlca[i]));
}
int lb = min(resp, db[a]-resp);
for(int i = 0; i < n; i++){
if(dlca[i] < lb)
bsub[i] = 1;
}
// ao parear os indices e considerar apenas aqueles que estão no mesmo grupo,
// caso haja um majoritário ele será majoritário tanto no vetor inicial quanto no modificado
stack<int,vector<int>> st;
vector<bool> par(n,0); // verdadeiro se x estiver pareado
for(int i = 0; i < (n>>1); i++){
int cur = 2*i;
//cout << "check(" << cur << "," << cur+1 << ") = " << check(cur,cur+1,bsub,db, lb,a) << '\n';
if(!check(cur,cur+1,bsub,db, lb,a))
continue;
par[cur] = 1;
par[cur+1] = 1;
if(st.empty()){
st.push(cur);
} else {
//cout << "check(" << st.top() << "," << cur << ") = " << check(st.top(), cur, bsub,db,lb,a) << '\n';
if(check(st.top(), cur, bsub,db,lb,a))
st.push(cur);
else st.pop();
}
}
int major = (st.empty() ? n-1 : st.top());
cout << "pares ->";
for(bool i : par)
cout << i;
cout << '\n';
int majorcount = 0;
for(int i = 0; i < n; i++){
if(par[i]){
if(i&1)
continue;
//cout << "check(" << i << "," << major << ") = " << check(i,major,bsub,db,lb,a) << '\n';
if(check(i,major,bsub,db,lb,a))
majorcount+=2;
} else {
//cout << "check(" << i << "," << major << ") = " << check(i,major,bsub,db,lb,a) << '\n';
if(check(i,major,bsub,db,lb,a))
majorcount++;
}
}
cout << major << ' ' << majorcount << "\n";
if(majorcount > (n>>1))
resp*=-1;
return resp;
}
