제출 #970819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
970819		vjudge1	Gap (APIO16_gap)	C++14	49.72 / 100	34 ms	4204 KiB

gap

#include "gap.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int dnc(int l, int r){
   if (l>=r) return 0;
   int mid=(l+r)>>1;
   int l1, r1, l2, r2;
   MinMax(l, mid, &l1, &r1);
   MinMax(mid+1, r, &l2, &r2);
   int ll=l1;
   if (ll==-1) ll=l2;
   int rr=r2;
   if (rr==-1) rr=r1;
   if (ll==-1 || rr==-1) return r-l+2;
   int ans=max({(r+1)-rr, ll-(l-1), (l2==-1 || r1==-1)?0:l2-r1});
   if (ans<r1-l1) ans=max(ans, dnc(l1+1, r1-1));
   if (ans<r2-l2) ans=max(ans, dnc(l2+1, r2-1));
   return ans;
}

long long findGap(int32_t T, int32_t 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;
   return dnc(l+1, r-1);
}

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