답안 #1005214

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1005214	2024-06-22T08:59:51 Z	우민규(#10879)	Shortcut (IOI16_shortcut)	C++14	0 / 100	0 ms	440 KB

shortcut

#include "shortcut.h"

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

long long find_shortcut(int n, vector<int> l, vector<int> d, int c) {
  vector<int64_t> x(n), xpdsfx_xmd_min(n + 1);
  vector<pair<int64_t, int>> xpd(n);

  x[0] = 0;
  for (int i = 0; i < n - 1; ++i) x[i + 1] = x[i] + l[i];
  for (int i = 0; i < n; ++i) xpd[i] = {x[i] + d[i], i};
  sort(xpd.begin(), xpd.end());
  xpdsfx_xmd_min[n] = INT64_MAX;
  for (int i = n - 1; i >= 0; --i)
    xpdsfx_xmd_min[i] =
        min(xpdsfx_xmd_min[i + 1], x[xpd[i].second] - d[xpd[i].second]);

  // rect of [a, b] transpose w. length <= l
  auto find_rect = [&](int64_t l) -> array<int64_t, 4> {
    int64_t gpl = INT64_MIN, gpu = INT64_MAX, gml = INT64_MIN, gmu = INT64_MAX;
    for (int u = 0; u < n; ++u) {
      // |u-v| > l- d[u] - d[v]
      // v < u: pass
      // u < v: v-u > l-d[u] - d[v]g
      // v + d[v] > l + u - d[u]
      // xpd[v] > l + u - d[u]
      int v_lower = upper_bound(xpd.begin(), xpd.end(),
                                make_pair(l + x[u] - d[u], INT_MAX)) -
                    xpd.begin();
      if (v_lower == xpd.size()) continue;
      // for v in xpd[v_lower..]
      // xpd[u] + xpd[v] - (l-c) max
      int64_t pl = (x[u] + d[u]) + xpd.back().first - (l - c);
      // xmd[u] + xmd[v] + (l-c) min
      int64_t pu = (x[u] - d[u]) + xpdsfx_xmd_min[v_lower] + (l - c);
      // -xmd[u] + xpd[v] - (l-c) max
      int64_t ml = -(x[u] - d[u]) + xpd.back().first - (l - c);
      // -xpd[u] + xmd[v] + (l-c) min
      int64_t mu = -(x[u] + d[u]) + xpdsfx_xmd_min[v_lower] + (l - c);

      gpl = max(gpl, pl), gpu = min(gpu, pu);
      gml = max(gml, ml), gmu = min(gmu, mu);
    }
    return {gpl, gpu, gml, gmu};
  };
  auto conatins_lattice_point = [&](array<int64_t, 4> rect) -> bool {
    auto [pl, pu, ml, mu] = rect;
    if (pl > pu || ml > mu) return false;
    if (pl == INT64_MIN) {
      assert(pu == INT64_MAX && ml == INT64_MIN && mu == INT64_MAX);
      return true;
    }
    for (int a = 0; a < n; ++a) {
      // pl <= a+b <= pu
      // ml <= b-a <= mu
      // pl - a <= b <= pu - a
      // ml + a <= b <= mu + a
      int64_t bl = max(pl - x[a], ml + x[a]);
      int64_t bu = min(pu - x[a], mu + x[a]);
      if (lower_bound(x.begin(), x.end(), bl) !=
          upper_bound(x.begin(), x.end(), bu)) {
        return true;
      }
    }
    return false;
  };
  int64_t ll = 0, lu = INT64_MAX;
  // diameter <= ll impos, <= lu pos
  while (ll + 1 < lu) {
    int64_t lm = ll + (lu - ll) / 2;
    if (conatins_lattice_point(find_rect(lm))) {
      // lm possible
      lu = lm;
    } else {
      ll = lm;
    }
  }
  return lu;
}

#ifndef EVAL
#include "grader.cpp"
#endif

Compilation message

shortcut.cpp: In lambda function:
shortcut.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |       if (v_lower == xpd.size()) continue;
      |           ~~~~~~~~^~~~~~~~~~~~~
shortcut.cpp: In lambda function:
shortcut.cpp:48:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     auto [pl, pu, ml, mu] = rect;
      |          ^

Subtask #1
0 / 9.0

#	결과	메모리	Grader output
1	Correct	344 KB	n = 4, 80 is a correct answer
2	Correct	436 KB	n = 9, 110 is a correct answer
3	Correct	348 KB	n = 4, 21 is a correct answer
4	Correct	348 KB	n = 3, 4 is a correct answer
5	Incorrect	440 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #2
0 / 14.0

#	결과	메모리	Grader output
1	Correct	344 KB	n = 4, 80 is a correct answer
2	Correct	436 KB	n = 9, 110 is a correct answer
3	Correct	348 KB	n = 4, 21 is a correct answer
4	Correct	348 KB	n = 3, 4 is a correct answer
5	Incorrect	440 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #3
0 / 8.0

#	결과	메모리	Grader output
1	Correct	344 KB	n = 4, 80 is a correct answer
2	Correct	436 KB	n = 9, 110 is a correct answer
3	Correct	348 KB	n = 4, 21 is a correct answer
4	Correct	348 KB	n = 3, 4 is a correct answer
5	Incorrect	440 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #4
0 / 7.0

#	결과	메모리	Grader output
1	Correct	344 KB	n = 4, 80 is a correct answer
2	Correct	436 KB	n = 9, 110 is a correct answer
3	Correct	348 KB	n = 4, 21 is a correct answer
4	Correct	348 KB	n = 3, 4 is a correct answer
5	Incorrect	440 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #5
0 / 33.0

#	결과	메모리	Grader output
1	Correct	344 KB	n = 4, 80 is a correct answer
2	Correct	436 KB	n = 9, 110 is a correct answer
3	Correct	348 KB	n = 4, 21 is a correct answer
4	Correct	348 KB	n = 3, 4 is a correct answer
5	Incorrect	440 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #6
0 / 22.0

#	결과	메모리	Grader output
1	Correct	344 KB	n = 4, 80 is a correct answer
2	Correct	436 KB	n = 9, 110 is a correct answer
3	Correct	348 KB	n = 4, 21 is a correct answer
4	Correct	348 KB	n = 3, 4 is a correct answer
5	Incorrect	440 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #7
0 / 4.0

#	결과	메모리	Grader output
1	Correct	344 KB	n = 4, 80 is a correct answer
2	Correct	436 KB	n = 9, 110 is a correct answer
3	Correct	348 KB	n = 4, 21 is a correct answer
4	Correct	348 KB	n = 3, 4 is a correct answer
5	Incorrect	440 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-

Subtask #8
0 / 3.0

#	결과	메모리	Grader output
1	Correct	344 KB	n = 4, 80 is a correct answer
2	Correct	436 KB	n = 9, 110 is a correct answer
3	Correct	348 KB	n = 4, 21 is a correct answer
4	Correct	348 KB	n = 3, 4 is a correct answer
5	Incorrect	440 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 KB	-