Submission #970828

#	Time	Username	Problem	Language	Result	Execution time	Memory
970828		vjudge1	Gap (APIO16_gap)	C++14	30 / 100	46 ms	4248 KiB

gap

#include "gap.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

mt19937_64 rng(69420);

int rand(int l, int r){
   return uniform_int_distribution<int>(l, r)(rng);
}

long long findGap(int32_t T, int32_t N)
{
   int n=N;
   if (T==1){
      int pl=0, pr=1e18;
      vector<int> a;
      while (N>0){
         int l, r;
         MinMax(pl, pr, &l, &r);
         a.push_back(l);
         if (l!=r) a.push_back(r);
         pl=l+1;
         pr=r-1;
         N-=2;
      }
      sort(a.begin(), a.end());
      int ans=0;
      for (int i=1; i<(int)a.size(); ++i) ans=max(ans, a[i]-a[i-1]);
      return ans;
   }
   int l, r;
   MinMax(0, 1e18, &l, &r);
   if (N==2) return r-l;
   if (r-l==2) return 1;
   int min_ans=(r-l)/(n-1);
   int ans=0;
   int lst=l;
   while (1){
      int ll=l+1, rr=ll+min_ans-1;
      if (rr>=r) break;
      int tl, tr;
      MinMax(ll, rr, &tl, &tr);
      if (tr==-1) l=rr;
      else{
         ans=max(ans, tl-lst);
         lst=tr;
         l=tr;
      }
   }
   return max(ans, r-lst);
}

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