Submission #798278

#	Time	Username	Problem	Language	Result	Execution time	Memory
798278		erray	Rail (IOI14_rail)	C++17	100 / 100	92 ms	99012 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/codes/ioi14_d1/debug.h"
#else 
  #define debug(...) void(37)
#endif

template<typename T> 
vector<T> inverse_fuck(T* a, int N) {
  vector<T> res(N);
  for (int i = 0; i < N; ++i) {
    res[i] = a[i];
  }
  return res;
}

const int MAX = int(2e6);
void findLocation(int N, int first, int location[], int stype[])  {
  location[0] = first, stype[0] = 1;
  if (N == 1) {
    return;
  }
  vector<vector<int>> mem(N, vector<int>(N));
  auto Dist = [&](int i, int j) {
    if (i > j) {
      swap(i, j);
    }
    return mem[i][j] = (mem[i][j] != 0 || i == j ? mem[i][j] : getDistance(i, j));
  };
  int match = 1;
  for (int i = 2; i < N; ++i) {
    debug(Dist(0, i));
    if (Dist(0, i) < Dist(0, match)) {
      match = i;
    }
  }
  debug(match);
  vector<int> between, left, right;
  for (int i = 1; i < N; ++i) {
    if (i == match) {
      continue;
    }
    debug(Dist(match, i), Dist(0, i));
    if (Dist(match, i) + Dist(0, match) == Dist(0, i)) {
      if (Dist(0, i) < 2 * Dist(0, match)) {
        between.push_back(i);
      } else {
        left.push_back(i);
      }
    } else {
      right.push_back(i);
    }
  }
  auto Solve = [&](int root, vector<int> s, int fill) {
    sort(s.begin(), s.end(), [&](int x, int y) {
      return Dist(root, x) < Dist(root, y);
    });
    vector<int> placed = {fill};
    int last = root ^ match ^ 0;
    vector<tuple<int, int, int>> res;    
    int breaks = -1;
    vector<bool> used(MAX + 1);
    for (auto x : s) {
      int pos = -1, type = 0;
      int g = Dist(x, last); 
      int inside = Dist(root, last) - g;
      debug(g, inside, Dist(root, last));
      int next = int(lower_bound(placed.begin(), placed.end(), inside) - placed.begin());
      if (inside > fill && placed[next] != inside && 2 * placed[next] - inside == Dist(root, x)) {
        pos = inside;
        type = 0;        
      } else {
        pos = Dist(root, x);
        type = 1;
        last = x;
        placed.push_back(pos);
      }
      used[pos] = true;
      res.emplace_back(x, pos, type);
    }
    return res;
  };
  int fill = Dist(0, match);
  auto l = Solve(match, left, fill), r = Solve(0, right, fill);
  debug(left, l);
  debug(right, r);
  debug(between);
  for (auto[x, p, t] : r) {
    location[x] = p + location[0];
    stype[x] = t + 1;
  }
  for (auto x : between) {
    location[x] = location[0] + 2 * Dist(0, match) - Dist(0, x);
    stype[x] = 1;
  }
  for (auto[x, p, t] : l) {
    location[x] = location[0] + Dist(0, match) - p;
    stype[x] = (t ^ 1) + 1;
  }
  stype[match] = 2;
  location[match] = location[0] + Dist(0, match);
  for (int x = 0; x < N; ++x) {
    debug(x, location[x], stype[x]);
  }
  return;
}

Compilation message (stderr)

rail.cpp: In lambda function:
rail.cpp:65:9: warning: unused variable 'breaks' [-Wunused-variable]
   65 |     int breaks = -1;
      |         ^~~~~~

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