oj.uz

Submission #798278

# Submission time Handle Problem Language Result Execution time Memory
798278 2023-07-30T14:43:31 Z erray Rail (IOI14_rail) C++17
100 / 100
 92 ms 99012 KB 
#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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 652 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 652 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 652 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 648 KB Output is correct
10 Correct 1 ms 644 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 98940 KB Output is correct
2 Correct 79 ms 98936 KB Output is correct
3 Correct 83 ms 98952 KB Output is correct
4 Correct 83 ms 98940 KB Output is correct
5 Correct 84 ms 98944 KB Output is correct
6 Correct 83 ms 98956 KB Output is correct
7 Correct 82 ms 98912 KB Output is correct
8 Correct 78 ms 98920 KB Output is correct
9 Correct 80 ms 98864 KB Output is correct
10 Correct 88 ms 99012 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 98900 KB Output is correct
2 Correct 80 ms 98932 KB Output is correct
3 Correct 80 ms 98952 KB Output is correct
4 Correct 81 ms 98876 KB Output is correct
5 Correct 85 ms 98952 KB Output is correct
6 Correct 82 ms 98960 KB Output is correct
7 Correct 81 ms 98952 KB Output is correct
8 Correct 78 ms 98912 KB Output is correct
9 Correct 78 ms 98824 KB Output is correct
10 Correct 84 ms 98944 KB Output is correct
11 Correct 84 ms 98900 KB Output is correct
12 Correct 81 ms 98820 KB Output is correct
13 Correct 82 ms 98932 KB Output is correct
14 Correct 86 ms 98900 KB Output is correct
15 Correct 81 ms 98936 KB Output is correct
16 Correct 85 ms 98932 KB Output is correct
17 Correct 81 ms 98900 KB Output is correct
18 Correct 81 ms 98916 KB Output is correct
19 Correct 82 ms 98936 KB Output is correct
20 Correct 86 ms 98940 KB Output is correct