Submission #1007411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007411		tosivanmak	Rail (IOI14_rail)	C++17	100 / 100	70 ms	167560 KiB

rail

#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;
// }

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:140:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for(int i=0;i<hi.size();i++){
      |                 ~^~~~~~~~~~
rail.cpp:159:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for(int i=0;i<mi.size();i++){
      |                 ~^~~~~~~~~~
rail.cpp:139:13: warning: unused variable 'init2' [-Wunused-variable]
  139 |     ll init,init2;
      |             ^~~~~
rail.cpp:109:17: warning: 'init' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |     if(dist[i][j])return dist[i][j];
      |        ~~~~~~~~~^
rail.cpp:139:8: note: 'init' was declared here
  139 |     ll init,init2;
      |        ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44