제출 #7439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7439		gs13068	철로 (IOI14_rail)	C++98	30 / 100	156 ms	768 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;
  if(n>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]&&loc[sta[j].second]>loc[r]-rd&&(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[i].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]&&loc[sta[j].second]>loc[r]-rd&&(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: 22 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44