Submission #796901

#	Time	Username	Problem	Language	Result	Execution time	Memory
796901		qthang2k11	Rail (IOI14_rail)	C++17	30 / 100	47 ms	520 KiB

rail

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

const int N = 5003;

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

void findLocation(int n, int pos0, int a[], int t[]) {
  auto get = [&] (int l, int r) -> int {
    assert(l != r && l >= 0 && l < n && r >= 0 && r < n);
    return 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] = getDistance(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 j = 0; j < n; j++) {
      if (dist0[r] + to_r == dist0[x]) {
        apply(x, a[r] - to_r, 1);
        isApplied = true;
        break;
      }
      if (dist0[l] + to_l == dist0[x]) {
        apply(x, a[l] + to_l, 2);
        isApplied = true;
        break;
      }
    }
    if (!isApplied) apply(x, pos0 + dist0[x], 2);
  }
}

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