Submission #1008488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008488		SonicML	Rail (IOI14_rail)	C++14	100 / 100	49 ms	788 KiB

rail

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

using namespace std;

int const NMAX = 5000;
int pos[1 + NMAX];
int type[1 + NMAX];
int dist1[1 + NMAX];
int dist2[1 + NMAX];
int order1[1 + NMAX];
int order2[1 + NMAX];

int origin1, origin2;

int distAux[1 + NMAX];

bool compareOrder1(int a, int b) {
  return (dist1[a] < dist1[b]);
}

bool compareOrder2(int a, int b) {
  return (dist2[a] < dist2[b]);
}

void buildOrigin(int n, int first) {
  origin1 = 0;
  pos[origin1] = first;
  type[origin1] = 1;
  for(int i = 0;i < n;i++) {
    order1[i] = i;
    if(i != origin1) {
      dist1[i] = getDistance(origin1, i);
    }
  }
  sort(order1, order1+n, compareOrder1);
  origin2 = order1[1];
  pos[origin2] = pos[origin1] + dist1[origin2];
  type[origin2] = 2;
  dist2[origin1] = dist1[origin2];
  for(int i = 0;i < n;i++) {
    order2[i] = i;
    if(i != origin1 && i != origin2) {
      dist2[i] = getDistance(origin2, i);
    }
  }
  sort(order2, order2+n, compareOrder2);
  int newOrigin = order2[1];
  if(newOrigin != origin1) {
    pos[newOrigin] = pos[origin2] - dist2[newOrigin];
    type[newOrigin] = 1;
    //cerr << pos[origin1] << ' ' << pos[newOrigin] << '\n';
    for(int i = 0;i < n;i++) {
      if(i == origin1 || dist1[origin2] + dist2[i] == dist1[i]) {
        distAux[i] = dist2[newOrigin] + dist2[i];
      } else { 
        distAux[i] = dist1[i] - (pos[newOrigin] - pos[origin1]);
      }
    }
    origin1 = newOrigin;
    for(int i = 0;i < n;i++) {
      order1[i] = i;
      dist1[i] = distAux[i];
    }
    sort(order1, order1+n, compareOrder1);
  }
  return;
}

bool isLeft(int station) {
  return (dist1[origin2] + dist2[station] == dist1[station]);
}

void solveLeft(int n) {
  vector <int> pitstop;
  for(int i = 0;i < n;i++) {
    int station = order2[i];
    if(station != origin1 && station != origin2 && isLeft(station)) {
      if(pitstop.size() == 0) {
        pitstop.push_back(station);
        pos[station] = pos[origin2] - dist2[station];
        type[station] = 1;
      } else {
        int distJ = getDistance(pitstop[pitstop.size()-1], station);
        bool isGood = false;
        for(int j = pitstop.size()-1;j > 0 && !isGood;j--) {
          int indexJ = pitstop[j];
          if(dist2[indexJ] + distJ == dist2[station]) {
            isGood = true;
            pos[station] = pos[indexJ] + distJ;
            type[station] = 2;
          }
          int newJ = pitstop[j-1];
          distJ -= (pos[newJ] - pos[indexJ]);
        }
        if(!isGood) {
          int indexJ = pitstop[0];
          if(dist2[indexJ] + distJ == dist2[station]) {
            pos[station] = pos[indexJ] + distJ;
            type[station] = 2;
          } else {
            pitstop.push_back(station);
            pos[station] = pos[origin2] - dist2[station];
            type[station] = 1;
          }
        }
      }
    }
  }
  return;
}

void solveRight(int n) {
  vector <int> pitstop;
  for(int i = 0;i < n;i++) {
    int station = order1[i];
    if(station != origin1 && station != origin2 && !isLeft(station)) {
      if(pitstop.size() == 0) {
        pitstop.push_back(station);
        pos[station] = pos[origin1] + dist1[station];
        type[station] = 2;
      } else {
        int distJ = getDistance(pitstop[pitstop.size()-1], station);
        bool isGood = false;
        for(int j = pitstop.size()-1;j > 0 && !isGood;j--) {
          int indexJ = pitstop[j];
          if(dist1[indexJ] + distJ == dist1[station]) {
            isGood = true;
            pos[station] = pos[indexJ] - distJ;
            type[station] = 1;
          }
          int newJ = pitstop[j-1];
          distJ -= (pos[indexJ] - pos[newJ]);
        }
        if(!isGood) {
          int indexJ = pitstop[0];
          if(dist1[indexJ] + distJ == dist1[station]) {
            pos[station] = pos[indexJ] - distJ;
            type[station] = 1;
          } else {
            pitstop.push_back(station);
            pos[station] = pos[origin1] + dist1[station];
            type[station] = 2;
          } 
        }
      }
    }
  }
  return;
}

void findLocation(int n, int first, int location[], int stype[]) {
  if(n == 1) {
    location[0] = first;
    stype[0] = 1;
    return;
  }
  buildOrigin(n, first);  
  solveLeft(n);
  solveRight(n);
  for(int i = 0;i < n;i++) {
    location[i] = pos[i];
    stype[i] = type[i];
    //cerr << type[i] << ' ' << pos[i] << '\n';
    //debug[i] = i;
  }
  return;
}

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