Submission #797078

#	Time	Username	Problem	Language	Result	Execution time	Memory
797078		qthang2k11	Rail (IOI14_rail)	C++17	100 / 100	120 ms	98700 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 5003;

int dist0[N], p[N], dist[N][N];
bool xet[N];

void findLocation(int n, int pos0, int a[], int t[]) {
  memset(dist, -1, sizeof dist);
  for (int i = 0; i < n; i++) dist[i][i] = 0;
  auto get = [&] (int l, int r) -> int {
    assert(l != r && l >= 0 && l < n && r >= 0 && r < n);
    if (dist[l][r] != -1) return dist[l][r];
    return dist[l][r] = dist[r][l] = getDistance(l, r);
  };
  auto apply = [&] (int i, int pos, int type) -> void {
    a[i] = pos;
    t[i] = type;
  };
  apply(0, pos0, 1);
  if (n == 1) return;
  for (int i = 1; i < n; i++) dist0[i] = get(0, i);
  iota(p, p + n, 0);
  sort(p + 1, p + n, [] (int x, int y) {
    return dist0[x] < dist0[y];
  });
  int r = p[1], l = 0; 
  apply(r, pos0 + dist0[r], 2);
  for (int i = 2; i < n; i++) {
    int x = p[i], to_l = get(l, x), to_r = get(r, x);
    bool isApplied = false;
    for (int jj = 0; jj < i; jj++) {
      int j = p[jj];
      if (t[j] == 1 && a[r] - a[j] + (a[l] + to_l) - a[j] == to_r) {
        apply(x, a[l] + to_l, 2);
        isApplied = true;
        break;
      }
    }
    if (!isApplied) {
      for (int jj = 0; jj < i; jj++) {
        int j = p[jj];
        if (t[j] == 2 && a[j] - (a[r] - to_r) + dist0[j] == dist0[x]) {
          apply(x, a[r] - to_r, 1);
          isApplied = true;
          break;
        }
      }
    }
    if (!isApplied) apply(x, pos0 + dist0[x], 2);
    if (t[x] == 1 && a[x] < a[l]) l = x;
    if (t[x] == 2 && a[x] > a[r]) r = x;
  }
}

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