Submission #741570

#	Time	Username	Problem	Language	Result	Execution time	Memory
741570		baojiaopisu	Rail (IOI14_rail)	C++14	100 / 100	104 ms	572 KiB

rail

#include "rail.h"
#include <vector>
#include <algorithm>
using namespace std;

#define pb push_back

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const int N = 1e5 + 10;

int a[N], b[N];

void findLocation(int n, int first, int location[], int skype[]) {
  for(int i = 0; i < n; i++) skype[i] = 0;

  location[0] = first;
  skype[0] = 1;

  int pos = 0, D = 100000000;
  for(int i = 1; i < n; i++) {
    int x = getDistance(0, i);
    if(!pos) {
      pos = i;
      D = x;
    } else {
      if(D > x) {
        D = x;
        pos = i;
      }
    }
    a[i] = x;
  }

  location[pos] = first + D;
  skype[pos] = 2;

  for(int i = 1; i < n; i++) {
    if(i == pos) continue;
    int x = getDistance(pos, i);
    if(x < a[pos] && a[x] == a[pos] + x) {
      location[i] = location[pos] - x;
      skype[i] = 1;
    }
    b[i] = x;
  }

  vector<int> left, right;
  for(int i = 1; i < n; i++) {
    if(i == pos || skype[i]) continue;
    if(a[i] - b[i] >= a[pos]) left.pb(i);
    else right.pb(i);
  }

  sort(left.begin(), left.end(), [&](int x, int y) {
    return b[x] < b[y];
  });

  sort(right.begin(), right.end(), [&](int x, int y) {
    return a[x] < a[y];
  });

  vector<int> open;
  for(int i = 0; i < left.size(); i++) {
    int curr = left[i];
    if(i == 0) {
      open.pb(curr);
      location[curr] = location[pos] - b[curr];
      skype[curr] = 1;
      continue;
    }

    skype[curr] = 2;
    int x = getDistance(open.back(), curr);
    location[curr] = location[open.back()] + x;
    bool ok = (location[curr] < location[0]);
    for(int j = 0; j < n; j++) {
      if(curr != j) {
        ok &= (location[curr] != location[j]);
      }
    }
    if(!ok) {
      location[curr] = location[pos] - b[curr];
      open.pb(curr);
      skype[curr] = 1;
      continue;
    }

    int np = -1;
    for(int j = open.size() - 1; j >= 0; j--) {
      if(location[open[j]] < location[curr] && (np == -1 || location[open[j]] > location[open[np]])) np = j;
    }

    if(location[curr] - location[open[np]] + location[pos] - location[open[np]] == b[curr]) continue;
    location[curr] = location[pos] - b[curr];
    open.pb(curr);
    skype[curr] = 1;
  } 

  vector<int> close;
  for(int i = 0; i < right.size(); i++) {
    int curr = right[i];
    if(i == 0) {
      close.pb(curr);
      location[curr] = location[0] + a[curr];
      skype[curr] = 2;
      continue;
    }

    skype[curr] = 1;
    int x = getDistance(close.back(), curr);
    location[curr] = location[close.back()] - x;
    bool ok = (location[curr] > location[pos]);
    for(int j = 0; j < n; j++) {
      if(curr != j) ok &= (location[curr] != location[j]);
    }
    if(!ok) {
      location[curr] = location[0] + a[curr];
      close.pb(curr);
      skype[curr] = 2;
      continue;
    }

    int np = -1;
    for(int j = close.size() - 1; j >= 0; j--) {
      if(location[close[j]] > location[curr] && (np == -1 || location[close[j]] < location[close[np]])) np = j;
    }

    if(location[close[np]] - location[curr] + location[close[np]] - location[0] == a[curr]) continue;
    location[curr] = location[0] + a[curr];
    close.pb(curr);
    skype[curr] = 2;
  }

  // for(int i = 0; i < n; i++) {
  //   cout << "debug " << skype[i] << " " << location[i] << endl;
  // }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int i = 0; i < left.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
rail.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for(int i = 0; i < right.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~

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