#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include "rail.h" #include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define pb push_back const int mxn = 5000, inf = 1e9; int dist[4][mxn]; bool comp(int i, int j){ return dist[0][i] < dist[0][j]; } void findLocation(int N, int first, int location[], int stype[]){ location[0] = first; stype[0] = 1; if(N==1) return; int piv1 = 1; for(int i = 1; i < N; i++){ dist[0][i] = getDistance(0,i); if(dist[0][i] < dist[0][piv1]) piv1 = i; } location[piv1] = location[0] + dist[0][piv1]; stype[piv1] = 2; for(int i = 1; i < N; i++) if(i!=piv1) dist[1][i] = getDistance(piv1,i); vector<int> comp1,comp2; for(int i = 1; i < N; i++) if(i!=piv1){ if(dist[1][i]+dist[0][piv1]==dist[0][i]) comp1.push_back(i); else comp2.push_back(i); } sort(comp1.begin(),comp1.end(),comp); sort(comp2.begin(),comp2.end(),comp); if(!comp1.empty()){ int piv = comp1[0]; location[piv] = location[piv1] - dist[1][piv]; stype[piv] = 1; set<pii> st; st.insert({location[piv],piv}); st.insert({location[0],0}); for(int i = 1; i < comp1.size(); i++){ int v = comp1[i]; int a = location[piv1] - dist[1][v]; auto it = st.lower_bound(make_pair(a+1,-1)); int cap = st.begin()->second; int req = getDistance(cap,v); int smt = 0; while(next(it) != st.end()){ int u = it->second; if(2*(it->first) - next(it)->first >= a){ it++; continue; } if(req - (location[u]-location[cap]) + dist[1][u] == dist[1][v]){ location[v] = -a + 2*location[u]; stype[v] = 2; smt = 1; break; } it++; } if(smt==0){ location[v] = a; stype[v] = 1; st.insert({a,v}); } } } if(!comp2.empty()){ int piv = comp2[0]; location[piv] = location[0] + dist[0][piv]; stype[piv] = 2; set<pii> st; st.insert({location[piv],piv}); st.insert({location[piv1],piv1}); for(int i = 1; i < comp2.size(); i++){ int v = comp2[i]; int a = location[0] + dist[0][v]; auto it = st.lower_bound(make_pair(a,-1)); int cap = prev(st.end())->second; int req = getDistance(v,cap); int smt = 0; while(prev(it) != st.begin()){ it--; if(2*(it->first) - prev(it)->first <= a) continue; int u = it->second; if(req - (location[cap]-location[u]) + dist[0][u] == dist[0][v]){ location[v] = -a + 2*location[u]; stype[v] = 1; smt = 1; break; } } if(smt==0){ location[v] = a; stype[v] = 2; st.insert({a,v}); } } } }