Submission #1141138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141138		fryingduc	Gap (APIO16_gap)	C++20	30 / 100	2095 ms	1988 KiB

gap

#include "gap.h"
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)
#endif

long long findGap(int T, int N) {
  if(T == 1) {
	  long long mn, mx;
	  MinMax(1, 1e18, &mn, &mx);
	  vector<long long> a(N + 1);
	  a[1] = mn, a[N] = mx;
	  for(int l = 2, r = N - 1; l <= r; ++l, --r) { 
	    MinMax(mn + 1, mx - 1, &a[l], &a[r]);
	    mn = a[l], mx = a[r];
    }
    long long res = 0;
    for(int i = 2; i <= N; ++i) {
      res = max(res, a[i] - a[i - 1]);
    }
    return res;
  } else {
    long long mn, mx;
    MinMax(1, 1e18, &mn, &mx);
    int b = (mx - mn + N - 2) / (N - 1) + 1;
    long long prv = mn, res = -1;
    long long l, r;
    for(long long i = mn; i <= mx; i += b) {
      if(i + b > mx) {
        MinMax(i, mx, &l, &r);
        if(l != -1) {
          res = max(res, l - prv);
        }
      } else {
        MinMax(i, i + b - 1, &l, &r);
        if(l != -1 and r != -1) {
          res = max(res, l - prv);
          prv = r;
        }
      }
    }
    return res;
  }
}

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