Submission #601550

#	Time	Username	Problem	Language	Result	Execution time	Memory
601550		Mamedov	Rail (IOI14_rail)	C++17	100 / 100	86 ms	588 KiB

rail

#pragma GCC optimize ("O3")
#include "rail.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void findLocation(int N, int first, int location[], int stype[]) {
  vector<pii>d0(N);
  d0[0] = mpr(0, 0);
  for (int i = 1; i < N; ++i) {
    d0[i].f = getDistance(0, i);
    d0[i].s = i;
  }
  location[0] = first;
  stype[0] = 1;
  sort(all(d0));

  if (N > 1) {
    int L = 0, R = d0[1].s;
    stype[R] = 2;
    location[R] = location[0] + d0[1].f;
    vector<pii>C, D;
    C.eb(mpr(-location[L], L));
    D.eb(mpr(location[R], R));
    for (int itr = 2; itr < N; ++itr) {
      int i = d0[itr].s;
      int dLi = getDistance(L, i);
      int dRi = getDistance(R, i);
      /// L i R   stype[i] = 1
      auto p = upper_bound(all(D), mpr(location[R] - dRi, i));
      if (location[R] - dRi > location[L] && p != D.end() && 2 * location[p->s] - dLi - location[L] == location[R] - dRi) {
        stype[i] = 1;
        location[i] = location[R] - dRi;
        continue;
      }
      /// L i R   stype[i] = 2
      p = upper_bound(all(C), mpr(-(location[L] + dLi), i));
      if (location[L] + dLi < location[R] && p != C.end() && dRi - location[R] + 2 * location[p->s] == location[L] + dLi) {
        stype[i] = 2;
        location[i] = location[L] + dLi;
        continue;
      }
      /// i L R
      if (d0[itr].f == d0[1].f + dRi - (location[R] - location[d0[1].s])) {
        stype[i] = 1;
        location[i] = location[R] - dRi;
        C.eb(mpr(-location[i], i));
        L = i;
      } else {
        /// L R i
        stype[i] = 2;
        location[i] = location[L] + dLi;
        D.eb(mpr(location[i], i));
        R = i;
      }
    }
  }
}

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