Submission #398506

#	Time	Username	Problem	Language	Result	Execution time	Memory
398506		MKopchev	Rail (IOI14_rail)	C++14	100 / 100	89 ms	780 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
/*
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;
  }
  //cout<<"getDistance "<<x<<" "<<y<<" -> "<<ret<<endl;

  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 my_location[10005],my_stype[10005],my_n;

int inf=1e9;

int d_after(int y)
{
    int ret=inf;

    for(int i=0;i<my_n;i++)
        if(my_stype[i]==2&&my_location[i]>my_location[y])
            ret=min(ret,my_location[i]);

    assert(ret!=inf);

    return ret;
}
int d_before(int x)
{
    int ret=-inf;

    for(int i=0;i<my_n;i++)
        if(my_stype[i]==1&&my_location[i]<my_location[x])
            ret=max(ret,my_location[i]);

    assert(ret!=-inf);

    return ret;
}

int manual_dist(int x,int y)
{
    if(x==y)return 0;

    if(my_location[x]>my_location[y])swap(x,y);

    //cout<<"manual "<<x<<" "<<y<<" "<<my_stype[x]<<" "<<my_stype[y]<<endl;

    if(my_stype[x]==1&&my_stype[y]==2)return my_location[y]-my_location[x];
    if(my_stype[x]==1&&my_stype[y]==1)return 2*d_after(y)-my_location[y]-my_location[x];
    if(my_stype[x]==2&&my_stype[y]==2)return my_location[x]+my_location[y]-2*d_before(x);
    return my_location[x]-2*d_before(x)+2*d_after(y)-my_location[y];
}

bool allow(int pos)
{
    for(int i=0;i<my_n;i++)
        if(my_location[i]==my_location[pos]&&i!=pos)return 0;
    return 1;
}

map<int,int> seen;
void findLocation(int N, int first, int location[], int stype[])
{
    my_n=N;

    vector< pair<int,int> > d={};

	for(int i=1;i<N;i++)
        d.push_back({getDistance(0,i),i});

    sort(d.begin(),d.end());

    my_stype[0]=1;
    my_location[d[0].second]=d[0].first;
    my_stype[d[0].second]=2;

    seen[0]=1;
    seen[d[0].first]=2;

    int most_left=0,most_right=d[0].second;

    /*
    cout<<"first= "<<first<<endl;
    for(int i=0;i<N;i++)cout<<i<<" -> "<<my_location[i]<<" "<<my_stype[i]<<endl;
    cout<<"---"<<endl;
    */

	for(int i=1;i<d.size();i++)
    {
        int pos=d[i].second;

        int dist_0=d[i].first;

        int dist_l=getDistance(most_left,pos);
        int dist_r=getDistance(pos,most_right);

        int av=(my_location[most_left]+my_location[most_right]+dist_l-dist_r)/2;

        bool ok=1;
        if(seen.count(av))
        {
            ok=(seen[av]!=1);
            //cout<<"type seen"<<endl;
        }
        else
        {
            ok=(av<0);
            //cout<<"type direct"<<endl;
        }

        pair<int,int> possible_l={my_location[most_right]-(dist_r),1};
        pair<int,int> possible_r={my_location[most_left]+(dist_l),2};

        /*
        cout<<"pos= "<<pos<<" dist_0= "<<dist_0<<" dist_l= "<<dist_l<<" dist_r= "<<dist_r<<" most_left= "<<most_left<<" most_right= "<<most_right<<endl;
        cout<<"av= "<<av<<endl;
        */

        if(ok)
        {
            my_location[pos]=possible_l.first;
            my_stype[pos]=possible_l.second;
        }
        else
        {
            my_location[pos]=possible_r.first;
            my_stype[pos]=possible_r.second;
        }

        if(my_stype[pos]==1)
        {
            if(my_location[pos]<my_location[most_left])most_left=pos;
        }
        else
        {
            if(my_location[pos]>my_location[most_right])most_right=pos;
        }

        //cout<<pos<<" -> "<<my_location[pos]<<" "<<my_stype[pos]<<endl;
        seen[my_location[pos]]=my_stype[pos];
    }

    for(int i=0;i<N;i++)
    {
        location[i]=my_location[i];
        stype[i]=my_stype[i];
    }

    for(int i=0;i<N;i++)
        location[i]+=first;

    //for(int i=0;i<N;i++)cout<<i<<" -> "<<location[i]<<" "<<stype[i]<<endl;
}
/*
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++)
    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:183:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |  for(int i=1;i<d.size();i++)
      |              ~^~~~~~~~~
rail.cpp:187:13: warning: unused variable 'dist_0' [-Wunused-variable]
  187 |         int dist_0=d[i].first;
      |             ^~~~~~

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