Submission #720039

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
720039	2023-04-07 10:01:58	Forested	Gap (APIO16_gap)	C++17	100 / 100	63 ms	1076 KiB

gap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "gap.h"
#include <algorithm>
long long findGap(int t, int n) {
  if (t == 1) {
    long long ans = 0;
    long long pmn = -1, pmx = 1000000000000000001, mn = -1, mx = -1;
    for (int i = 0; i < (n + 1) / 2; ++i) {
      MinMax(pmn + 1, pmx - 1, &mn, &mx);
      if (i != 0) {
        ans = std::max({ans, mn - pmn, pmx - mx});
      }
      pmn = mn;
      pmx = mx;
    }
    ans = std::max(ans, pmx - pmn);
    return ans;
  }
  long long mn = -1, mx = -1;
  MinMax(0, 1000000000000000000, &mn, &mx);
  long long l = mn, h = mx;
  long long w = (h - l + n - 1) / n;
  long long cur = l + 1, pmx = l, ans = 0;
  while (cur <= h) {
    MinMax(cur, cur + w - 1, &mn, &mx);
    if (mn != -1) {
      if (pmx != -1) {
        ans = std::max(ans, mn - pmx);
      }
      pmx = mx;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70