Submission #950927

#	Time	Username	Problem	Language	Result	Execution time	Memory
950927		kilkuwu	Gap (APIO16_gap)	C++17	100 / 100	44 ms	4224 KiB

gap

#include <bits/stdc++.h>

#ifndef LOCAL
#include "gap.h"
#else

void MinMax(long long, long long, long long*, long long*);

static void my_assert(int k){ if (!k) exit(1); }


long long findGap(int, int);

static int subtask_num, __N;
static long long A[100001];
static long long call_count;
void MinMax(long long s, long long t, long long *mn, long long *mx) {
  int lo = 1, hi = __N, left = __N+1, right = 0;
  my_assert(s <= t && mn != NULL && mx != NULL);
  while (lo <= hi){
    int mid = (lo+hi)>>1;
    if (A[mid] >= s) hi = mid - 1, left = mid;
    else lo = mid + 1;
  }
  lo = 1, hi = __N;
  while (lo <= hi){
    int mid = (lo+hi)>>1;
    if (A[mid] <= t) lo = mid + 1, right = mid;
    else hi = mid - 1;
  }
  if (left > right) *mn = *mx = -1;
  else{
    *mn = A[left];
    *mx = A[right];
  }
  if (subtask_num == 1) call_count++;
  else if (subtask_num == 2) call_count += right-left+2;
}

int main()
{
  FILE *in = stdin, *out = stdout;
  my_assert(2 == fscanf(in, "%d%d", &subtask_num, &__N));
  my_assert(1 <= subtask_num && subtask_num <= 2);
  my_assert(2 <= __N && __N <= 100000);
  for (int i=1;i<=__N;i++) my_assert(1 == fscanf(in, "%lld", A+i));
  for (int i=1;i<__N;i++) my_assert(A[i] < A[i+1]);
  fprintf(out, "%lld\n", findGap(subtask_num, __N));
  fprintf(out, "%lld\n", call_count);
}
#endif
#ifdef LOCAL
#include "template\debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

struct Subtask1 {
  int n;

  Subtask1(int _n) : n(_n) {}

  long long solve() {
    std::vector<long long> a(n);

    MinMax(0, 1e18, &a[0], &a.back());

    for (int i = 1; i <= n - i - 1; i++) {
      MinMax(a[i - 1] + 1, a[n - i] - 1, &a[i], &a[n - i - 1]);
    }

    long long ans = a[1] - a[0];
    for (int i = 1; i + 1 < n; i++) {
      ans = std::max(ans, a[i + 1] - a[i]);
    }
    return ans;
  }
};


struct Subtask2 {
  int n;

  Subtask2(int _n) : n(_n) {}

  long long solve() {
    long long lo, hi;
    MinMax(0, 1e18, &lo, &hi);

    if (hi - lo + 1 == n) {
      return 1;
    }
    
    if (n == 2) {
      return hi - lo;
    }

    // we can do this 
  
    long long gap = (hi - lo - 1) / (n - 1);
    if (gap * (n - 1) < (hi - lo - 1)) gap++;
    dbg(gap);

    // we can do that now 
    std::vector<long long> values;
    values.push_back(lo);
    
    for (int i = 0; i < n - 1; i++) {
      long long ff = lo + 1 + gap * i;
      long long ee = lo + gap * (i + 1);
      ee = std::min(ee, hi - 1);

      if (ff > ee) continue;
      long long r1, r2;
      MinMax(ff, ee, &r1, &r2);
      if (r1 >= 0) {
        values.push_back(r1);
        if (r2 > r1) {
          values.push_back(r2);
        }
      }
    }

    values.push_back(hi);
    long long ans = 0;
    for (int i = 0; i + 1 < (int) values.size(); i++) {
      ans = std::max(ans, values[i + 1] - values[i]);
    }
    return ans;
  }
};

long long findGap(int T, int N) {
  if (T == 1) {
    Subtask1 sub1(N);
    return sub1.solve();
  } else {
    Subtask2 sub2(N);
    return sub2.solve();
  }
}

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