Submission #139096

#	Time	Username	Problem	Language	Result	Execution time	Memory
139096		toonewbie	Rail (IOI14_rail)	C++17	100 / 100	87 ms	888 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

void findLocation(int n, int first, int l[], int t[]) {
  l[0] = first;
  t[0] = 1;
  vector <pair <int, int>> v;
  for (int i = 1; i < n; i++) {
    v.push_back({getDistance(0, i), i});
  }
  sort(v.begin(), v.end());
  l[v[0].second] = first + v[0].first;
  t[v[0].second] = 2;
  set <int> C, D;
  C.insert(l[0]); D.insert(l[v[0].second]);
  int L = 0, R = v[0].second;
  for (int i = 1; i < v.size(); i++) {
    int id = v[i].second;
    int x = getDistance(id, L), y = getDistance(id, R);
    int lcan = l[L] + x, rcan = l[R] - y, res;
    auto it = --C.upper_bound(lcan);
    if (y == lcan - *it + l[R] - *it) {
      res = 1;
    } else {
      auto it = D.upper_bound(rcan);
      if (it != D.end() && x == *it - rcan + *it - l[L]) {
        res = 0;
      } else {
        if (v[i].first == 2 * l[v[0].second] - first - rcan) res = 0;
        else res = 1;
      }
    }
    if (res == 1) {
      l[id] = lcan;
      t[id] = 2;
      D.insert(l[id]);
      if (l[R] < l[id]) R = id;
    } else {
      l[id] = rcan;
      t[id] = 1;
      C.insert(l[id]);
      if (l[L] > l[id]) L = id;
    }
  }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:19:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < v.size(); i++) {
                   ~~^~~~~~~~~~

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