Submission #73291

#	Time	Username	Problem	Language	Result	Execution time	Memory
73291		funcsr	Rail (IOI14_rail)	C++17	100 / 100	206 ms	100296 KiB

rail

#include "rail.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
using namespace std;
typedef pair<int, int> P;

int cache[5001][5001];
int query(int x, int y) {
  if (cache[x][y] != -1) return cache[x][y];
  if (x == y) return cache[x][y] = 0;
  return cache[x][y] = cache[y][x] = getDistance(x, y);
}
#define DOWN 1
#define UP 2

void findLocation(int N, int pos0, int location[], int stype[]) {
  if (N == 1) {
    location[0] = pos0;
    stype[0] = 1;
    return;
  }

  rep(i, N) rep(j, N) cache[i][j] = -1;
  rep(i, N) location[i] = stype[i] = -1;
  location[0] = pos0;
  stype[0] = DOWN;
  P mp = P(INF, -1);
  rep(i, N) if (i != 0) mp = min(mp, P(query(0, i), i));
  int a = mp._2, d = mp._1;
  location[a] = pos0 + d;
  stype[a] = UP;
  int posa = location[a];

  vector<P> left, right;

  rep(i, N) if (i != 0 && i != a) {
    int d0 = query(0, i), da = query(a, i);
    if (d0 < d) {
      // (E)
      stype[i] = DOWN;
      location[i] = location[a]-da;
      assert(pos0 < location[i] && location[i] < location[a]);
    }
    else {
      if (d0-da == d) {
        // (A) or (B)
        left.pb(P(da-d, i));
      }
      else {
        // (C) or (D)
        right.pb(P(d0, i));
      }
    }
  }

  sort(all(left));
  int l = -1;
  map<int, bool> up;
  for (P p : left) {
    int r = p._1, b = p._2;
    if (l == -1) {
      location[b] = pos0-r;
      up[location[b]] = true;
      stype[b] = DOWN;
      l = b;
    }
    else {
      int s = (query(b, l) + r - (pos0-location[l]))/2;
      if (up[pos0 - (r-s)]) {
        location[b] = pos0-(r-s)+s;
        stype[b] = UP;
      }
      else {
        location[b] = pos0-r;
        up[location[b]] = true;
        stype[b] = DOWN;
        l = b;
      }
    }
  }

  sort(all(right));
  l = -1;
  up.clear();
  for (P p : right) {
    int r = p._1, b = p._2;
    if (l == -1) {
      location[b] = pos0+r;
      up[location[b]] = true;
      stype[b] = UP;
      l = b;
    }
    else {
      int s = (query(b, l) + r - (location[l]-pos0))/2;
      if (up[pos0 + (r-s)]) {
        location[b] = pos0+(r-s)-s;
        stype[b] = DOWN;
      }
      else {
        location[b] = pos0+r;
        up[location[b]] = true;
        stype[b] = UP;
        l = b;
      }
    }
  }
  rep(i, N) assert(location[i] != -1 && stype[i] != -1);
  rep(i, N) assert(0 <= location[i] && location[i] < 1000000);
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:41:7: warning: unused variable 'posa' [-Wunused-variable]
   int posa = location[a];
       ^~~~

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