| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1007410 | tosivanmak | Rail (IOI14_rail) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
// typedef struct Station {
// int index;
// int type;
// int location;
// int L,R;
// }STATION;
// long long cnt;
// static int S,SUBTASK;
// static STATION stations[10004];
// int cmp_fun_1(const void *a,const void *b)
// {
// STATION c,d;
// c = *(STATION*)(a);
// d = *(STATION*)(b);
// return c.location < d.location ? -1 : 1;
// }
// int cmp_fun_2(const void *a,const void *b)
// {
// STATION c,d;
// c = *(STATION*)(a);
// d = *(STATION*)(b);
// return c.index < d.index ? -1 : 1;
// }
// void now_I_want_to_getLR(){
// int now = stations[S-1].index,i;
// for(i=S-2;i>=0;i--){
// stations[i].R = now;
// if(stations[i].type==2) now = stations[i].index;
// }
// now = stations[0].index;
// for(i=1;i<S;i++){
// stations[i].L = now;
// if(stations[i].type==1) now = stations[i].index;
// }
// }
// int getDistance(int x,int y)
// {
// cnt++;
// if(x==y) return 0;
// if(x<0 || x>=S || y<0 || y>=S) return -1;
// if(stations[x].location > stations[y].location){
// int tmp = x;
// x = y;
// y = tmp;
// }
// int ret = 0;
// if(stations[x].type==1 && stations[y].type==1){
// ret = stations[stations[y].R].location-stations[x].location+stations[stations[y].R].location-stations[y].location;
// }else if(stations[x].type==1 && stations[y].type==2){
// ret = stations[y].location-stations[x].location;
// }else if(stations[x].type==2 && stations[y].type==2){
// ret = stations[x].location-stations[stations[x].L].location+stations[y].location-stations[stations[x].L].location;
// }else if(stations[x].type==2 && stations[y].type==1){
// ret = stations[x].location-stations[stations[x].L].location+stations[stations[y].R].location
// -stations[stations[x].L].location+stations[stations[y].R].location-stations[y].location;
// }
// return ret;
// }
// void getInput()
// {
// int g;
// g = scanf("%d",&SUBTASK);
// g = scanf("%d",&S);
// int s;
// for (s = 0; s < S; s++) {
// int type, location;
// g = scanf(" %d %d",&type,&location);
// stations[s].index = s;
// stations[s].location = location;
// stations[s].type = type;
// stations[s].L = -1;
// stations[s].R = -1;
// }
// qsort(stations, S, sizeof(STATION), cmp_fun_1);
// now_I_want_to_getLR();
// qsort(stations, S, sizeof(STATION), cmp_fun_2);
// }
// int serverGetStationNumber()
// {
// return S;
// }
// int serverGetSubtaskNumber()
// {
// return SUBTASK;
// }
// int serverGetFirstStationLocation()
// {
// return stations[0].location;
// }
ll dist[5005][5005];
ll hv[1000005];
ll getdist(ll i, ll j){
if(i==j)return 0;
if(dist[i][j])return dist[i][j];
dist[i][j]=dist[j][i]=getDistance(i,j);
return dist[i][j];
}
void findLocation(int n, int first, int location[],int stype[]){
location[0]=first,stype[0]=1;
hv[first]=1;
if(n==1)return;
int st=0;
vector<pair<ll,ll> >from,hi,mi;
for(int i=1;i<n;i++){
from.pb({getdist(st,i),i});
}
sort(from.begin(),from.end());
ll req=from[0].second;
location[req]=location[0]+getdist(0,req);stype[req]=2;hv[location[req]]=2;
for(int i=0;i<n;i++){
if(i==st||i==req)continue;
if(getdist(st,i)==getdist(req,i)+getdist(st,req)&&getdist(req,i)<getdist(st,req)){
stype[i]=1;location[i]=location[req]-getdist(req,i);continue;
}
if(getdist(st,i)==getdist(req,i)+getdist(st,req)){
hi.push_back({getdist(req,i),i});
}
else{
mi.push_back({getdist(st,i),i});
}
}
sort(hi.begin(),hi.end());
sort(mi.begin(),mi.end());
ll init,init2;
for(int i=0;i<hi.size();i++){
if(i==0){
ll nd=hi[i].second;
stype[nd]=1,location[nd]=location[req]-getdist(req,nd);
hv[location[nd]]=1;
init=nd;continue;
}
ll nd=hi[i].second;
ll v=getdist(init,nd)+getdist(req,nd)-getdist(init,req);v/=2;
if(location[init]+getdist(init,nd)-v)>=0&&hv[location[init]+getdist(init,nd)-v]==1){
location[nd]=location[init]+getdist(nd,init);
stype[nd]=2;
}
else{
location[nd]=location[req]-getdist(nd,req);
stype[nd]=1;init=nd;
}
hv[location[nd]]=stype[nd];
}
for(int i=0;i<mi.size();i++){
if(i==0){
ll nd=mi[i].second;
stype[nd]=2,location[nd]=location[st]+getdist(st,nd);
hv[location[nd]]=2;
init=nd;continue;
}
ll nd=mi[i].second;
ll v=getdist(init,nd)+getdist(st,nd)-getdist(init,st);v/=2;
if(location[init]+getdist(init,nd)-v)>=0&&hv[location[init]-getdist(init,nd)+v]==2){
location[nd]=location[init]-getdist(nd,init);
stype[nd]=1;
}
else{
location[nd]=location[st]+getdist(nd,st);
stype[nd]=2;init=nd;
}
hv[location[nd]]=stype[nd];
}
}
// int main()
// {
// int i;
// getInput();
// cnt = 0;
// int location[10005];
// int type[10005];
// int ok = 1;
// findLocation(S, serverGetFirstStationLocation(),location, type);
// if(SUBTASK==3 && cnt>S*(S-1)) ok = 0;
// if(SUBTASK==4 && cnt>3*(S-1)) ok = 0;
// for (i = 0; i < S; i++){
// cout<<type[i]<<" "<<location[i]<<'\n';
// }
// if(ok==0) printf("Incorrect");
// else printf("Correct");
// return 0;
// }