Submission #990253

#	Time	Username	Problem	Language	Result	Execution time	Memory
990253		huutuan	Rail (IOI14_rail)	C++14	100 / 100	60 ms	102740 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>

using namespace std;

const int N=5010, M=1e6+10;
int n;
int mem[N][N], tt[M];

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_;
   pos[0]=first;
   t[0]=1; tt[pos[0]]=1;
   int ir=1;
   for (int i=1; i<n; ++i) if (dist(0, i)<dist(0, ir)) ir=i;
   pos[ir]=pos[0]+dist(0, ir); t[ir]=2; tt[pos[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)+dist(il, ir)){
         if (dist(i, ir)<dist(il, ir)){
            pos[i]=pos[ir]-dist(i, ir);
            t[i]=1; tt[pos[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 (tt[p]==2){
         pos[i]=pos[rr]-dist(rr, i);
         t[i]=1; tt[pos[i]]=1;
      }else{
         pos[i]=pos[ll]+dist(ll, i);
         t[i]=2; tt[pos[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 (tt[p]==1){
         pos[i]=pos[ll]+dist(ll, i);
         t[i]=2; tt[pos[i]]=2;
      }else{
         pos[i]=pos[rr]-dist(rr, i);
         t[i]=1; tt[pos[i]]=1;
         ll=i;
      }
   }
   for (int i:vl) assert(pos[i]<pos[ir]);
   for (int i:vr) assert(pos[i]>pos[il]);
}

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