Submission #990248

#	Time	Username	Problem	Language	Result	Execution time	Memory
990248		huutuan	Rail (IOI14_rail)	C++14	30 / 100	54 ms	98900 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>

using namespace std;

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

int dist(int i, int j){
   if (i==j) return 0;
   if (mem[i][j]!=-1) return mem[i][j];
   return mem[i][j]=mem[j][i]=getDistance(i, j);
}

void findLocation(int N_, int first, int pos[], int t[])
{
   memset(mem, -1, sizeof mem);
   n=N_;
   for (int i=0; i<n; ++i){
      pos[i]=-1;
      d0[i]=dist(i, 0);
   }
   pos[0]=first;
   t[0]=1;
   int ir=1;
   for (int i=1; i<n; ++i) if (d0[i]<d0[ir]) ir=i;
   pos[ir]=pos[0]+d0[ir]; t[ir]=2;
   int il=0;
   vector<int> vl, vr;
   for (int i=0; i<n; ++i) if (i!=ir && i!=il){
      if (dist(i, il)>dist(i, ir)){
         if (dist(i, ir)<dist(il, ir)){
            pos[i]=pos[ir]-dist(i, ir);
            t[i]=1;
         }else vl.push_back(i);
      }else{
         vr.push_back(i);
      }
   }
   sort(vl.begin(), vl.end(), [&](int x, int y){ return dist(il, x)<dist(il, y); });
   sort(vr.begin(), vr.end(), [&](int x, int y){ return dist(il, x)<dist(il, y); });
   int ll=il, rr=ir;
   for (int i:vr){
      int p=(dist(ll, i)-dist(rr, i)+pos[ll]+pos[rr])/2;
      if (p==pos[rr]){
         pos[i]=pos[rr]-dist(rr, i);
         t[i]=1;
      }else{
         pos[i]=pos[ll]+dist(ll, i);
         t[i]=2;
         rr=i;
      }
   }
   ll=il, rr=ir;
   for (int i:vl){
      int p=(dist(ll, i)-dist(rr, i)+pos[ll]+pos[rr])/2;
      if (p==pos[ll]){
         pos[i]=pos[ll]+dist(ll, i);
         t[i]=2;
      }else{
         pos[i]=pos[rr]-dist(rr, i);
         t[i]=1;
         ll=i;
      }
   }
}

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