Submission #1213679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213679		loom	Gap (APIO16_gap)	C++20	30 / 100	2096 ms	1984 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 5e18
#define nl '\n'
 
ll findGap(int t, int n){
	if(t == 1){
      vector<ll> vl, vr;
      ll l = 0, r = 1e18, cnt = 0, ans = 0;

      while(cnt < n){
         ll mn = l, mx = r;
         MinMax(l, r, &mn, &mx);
         if(mn == -1) break;

         if(!vl.empty()) ans = max(ans, mn - vl.back());
         vl.push_back(mn);
         cnt++;

         if(mn == mx) break;

         if(!vr.empty()) ans = max(ans, vr.back() - mx);
         vr.push_back(mx);
         cnt++;

         l = mn+1;
         r = mx-1;
      }
      
      ans = max(ans, vr.back() - vl.back());
      return ans;
   }

   ll mn, mx;
   MinMax(0, 1e18, &mn, &mx);
   ll g = (mx-mn-1)/(n-1) + 1;

   ll ans = g, p = mn, maxi = mx;
   for(int i = mn+1; i < maxi; i += g+1){
      MinMax(i, min(i+g, maxi-1), &mn, &mx);
      ans = max(ans, mn - p);
      p = mx;
   }

   ans = max(ans, maxi - p);
   return ans;
}
 

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