Submission #1026769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026769		dozer	Rail (IOI14_rail)	C++14	100 / 100	48 ms	852 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt","w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2
#define mid (l + r) / 2
#define ll long long
#define MAXN 200005


const int modulo = 1e9 + 7;
const ll INF = 2e18 +7;

int getDistance(int x,int y);

void findLocation(int N, int first, int location[], int stype[])
{
    vector<int> dist1(N, 0), done(N, 0);
    pii mini = {modulo, 0};
    for (int i = 1; i < N; i++){
        dist1[i] = getDistance(0, i);
        mini = min(mini, {dist1[i], i});
    }

    int D = mini.nd;
    stype[D] = 2;
    stype[0] = 1;
    location[D] = mini.st + first;
    location[0] = first;

    done[0] = done[D] = 1;
    vector<int> dist2(N, 0);
    dist2[0] = dist1[D];

    //cout<<D<<sp<<location[D]<<sp<<dist1[D]<<endl;
    mini = {first, 0};
    vector<int> lft, rgt;

    for (int i = 1; i < N; i++){
        if (i == D) continue;
        dist2[i] = getDistance(D, i);

        if (dist1[i] == dist2[i] + dist1[D]){
            lft.pb(i);
        }
        else rgt.pb(i);
    }

    sort(lft.begin(), lft.end(), [&](int a, int b){
        return dist2[a] < dist2[b];
    });

    if (!lft.empty()){
        vector<int> cs;
        int lst = lft.front();
        stype[lst] = 1; // C
        location[lst] = location[D] - dist2[lst];
        done[lst] = 1;
        cs.pb(-location[lst]);
        for (int i = 1; i < lft.size(); i++){
            int curr = lft[i];
            int dist3 = getDistance(lst, curr);
            int tmp_loc = location[lst] + dist3;
            int pos = lower_bound(cs.begin(), cs.end(), -tmp_loc) - cs.begin();
            int tmp_dist = dist2[lst] + dist3 - 2 * (-location[lst] - cs[pos]);
            if (dist2[curr] == tmp_dist){
                stype[curr] = 2;
                location[curr] = tmp_loc;
                done[curr] = 1;
            }

            else{
                stype[curr] = 1;
                location[curr] = location[D] - dist2[curr];
                done[curr] = 1;
                lst = curr;
                cs.pb(-location[lst]);
            }
        }
    }

    sort(rgt.begin(), rgt.end(), [&](int a, int b){
        return dist1[a] < dist1[b];
    });

    if (!rgt.empty()){
        vector<int> ds;
        int lst = rgt.front();
        location[lst] = first + dist1[lst];
        stype[lst] = 2;
        ds.pb(location[lst]);
        for (int i = 1; i < rgt.size(); i++){
            int curr = rgt[i];
            int dist3 = getDistance(lst, curr);
            int tmp_loc = location[lst] - dist3;
            int pos = lower_bound(ds.begin(), ds.end(), tmp_loc) - ds.begin();
            int tmp_dist = dist3 + dist1[lst] - 2 * (location[lst] - ds[pos]);
            if (dist1[curr] == tmp_dist){
                stype[curr] = 1;
                location[curr] = tmp_loc;
                done[curr] = 1;
            }
            else{
                stype[curr] = 2;
                location[curr] = first + dist1[curr];
                done[curr] = 1;
                lst = curr;
                ds.pb(location[lst]);
            }
        }
    }
}
/*

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

int main()
{
    fileio();
    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 (int i = 0; i < S; i++){
        cout<<"("<<type[i]<<sp<<location[i]<<") ";
    }
    cout<<endl;

    for (int i = 0; i < S; i++){
        cout<<"("<<stations[i].type<<sp<<stations[i].location<<") ";
    }

    cout<<endl;
    for (i = 0; i < S; i++)
        if(type[i]!=stations[i].type || location[i]!=stations[i].location)
            ok = 0;


    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:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int i = 1; i < lft.size(); i++){
      |                         ~~^~~~~~~~~~~~
rail.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for (int i = 1; i < rgt.size(); i++){
      |                         ~~^~~~~~~~~~~~

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