Submission #990070

#	Time	Username	Problem	Language	Result	Execution time	Memory
990070		huutuan	Rail (IOI14_rail)	C++14	30 / 100	42 ms	656 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>

using namespace std;

const int N=5010;
int n, d0[N], d1[N];

void findLocation(int N_, int first, int pos[], int t[])
{
   n=N_;
   pos[0]=first;
   t[0]=1;
   pair<int, int> opt={(int)1e9, (int)1e9};
   for (int i=1; i<n; ++i) opt=min(opt, {d0[i]=getDistance(0, i), i});
   int id=opt.second, dist=opt.first;
   pos[id]=pos[0]+dist;
   t[id]=2;
   d1[0]=d0[id];
   for (int i=0; i<n; ++i) if (i!=id && i) d1[i]=getDistance(i, id);
   pair<int, int> min_c={pos[0], 0}, max_d={pos[id], id};
   for (int i=0; i<n; ++i) if (i!=id && i){
      if (d0[i]>=d1[i]){
         t[i]=1;
         if (d0[i]==d1[i]+d1[0]){
            pos[i]=pos[id]-d1[i];
            min_c=min(min_c, {pos[i], i});
         }else{
            pos[i]=-1;
         }
      }else{
         t[i]=2;
         if (d1[i]==d0[i]+d1[0]){
            pos[i]=pos[0]+d0[i];
            max_d=max(max_d, {pos[i], i});
         }else{
            pos[i]=-2;
         }
      }
   }
   for (int i=0; i<n; ++i){
      if (pos[i]==-1){
         pos[i]=max_d.first-getDistance(max_d.second, i);
      }
      if (pos[i]==-2){
         pos[i]=min_c.first+getDistance(min_c.second, i);
      }
   }
}

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