Submission #7436

#	Time	Username	Problem	Language	Result	Execution time	Memory
7436		gs13068	Rail (IOI14_rail)	C++98	8 / 100	171 ms	776 KiB

rail

#include "rail.h"
#include <algorithm>

std::pair<int,int> sta[5000];

void findLocation(int n,int fir,int loc[],int type[])
{
  int l,r;
  int ld,rd;
  int i,j,k;
  loc[0]=fir;
  type[0]=1;
  for(i=1;i<n;i++)
  {
    sta[i].first=getDistance(0,i);
    sta[i].second=i;
  }
  std::sort(sta+1,sta+n);
  loc[sta[1].second]=fir+sta[1].first;
  type[sta[1].second]=2;
  l=0;
  r=sta[1].second;
  for(i=2;i<n;i++)
  {
    ld=getDistance(l,sta[i].second);
    rd=getDistance(r,sta[i].second);
    k=-1;
    for(j=0;j<i;j++)if(type[sta[j].second]==2&&loc[sta[j].second]>loc[0]&&(k<0||loc[sta[j].second]<loc[sta[k].second]))k=j;
    if(k<0||loc[sta[k].second]-loc[0]+loc[sta[k].second]-(loc[r]-rd)!=sta[k].first)
    {
      loc[sta[i].second]=loc[l]+ld;
      type[sta[i].second]=2;
    }
    else
    {
      k=-1;
      for(j=0;j<i;j++)if(type[sta[j].second]==2&&loc[sta[j].second]>loc[l]&&(k<0||loc[sta[j].second]<loc[sta[k].second]))k=j;
      if(k<0||loc[sta[k].second]-loc[l]+loc[sta[k].second]-(loc[r]-rd)!=ld)
      {
        loc[sta[i].second]=loc[l]+ld;
        type[sta[i].second]=2;
      }
      else
      {
        loc[sta[i].second]=loc[r]-rd;
        type[sta[i].second]=1;
      }
    }
    if(type[sta[i].second]==1&&loc[sta[i].second]<loc[l])l=sta[i].second;
    if(type[sta[i].second]==2&&loc[sta[i].second]>loc[r])r=sta[i].second;
  }
}

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