제출 #797017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
797017		qthang2k11	철로 (IOI14_rail)	C++17	30 / 100	49 ms	512 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 < i; j++) {
      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 && a[p[1]] - (a[r] - to_r) + a[p[1]] - a[0] == dist0[x]) {
      apply(x, a[r] - to_r, 1);
      isApplied = true;
    }
    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: 0 / 26
• Subtask 4: 0 / 44