Submission #45381

#	Time	Username	Problem	Language	Result	Execution time	Memory
45381		OneSubmissionMan	Gap (APIO16_gap)	C++11	30 / 100	85 ms	2172 KiB

gap

# include "gap.h"
# include <bits/stdc++.h>

# define x first    
# define y second
# define mp make_pair
// everything go according to my plan      
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector         
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right  

using namespace std;

typedef pair <int, int> pii; 
typedef long long ll;
typedef long double ld;

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul

const ll N = 1e18;

ll solve_slow (int n) {
  ll a[n + 2];
  a[n + 1] = N + 1;
  a[0] = -1;
  for (int l = 1; l <= (n + 1) / 2; l++) {
    int r = n - l + 1;
    MinMax (a[l - 1] + 1, a[r + 1] - 1, a + l, a + r);
  }          
  ll ans = 0;
  for (int i = 1; i < n; i++)
    ans = max (ans, a[i + 1] - a[i]);
  return ans;
}

long findGap (int t, int n) {  
  return solve_slow (n);
  ll ans = 0;

  ll F, S;
  MinMax (1ll, N, &F, &S);        
  ll len = max (1ll, (S - F - 1) / (n - 1));

  ll f = F;          
  for (int i = 1; i <= n-2; i++) {  
    ll x, y;
    MinMax (f + 1, f + len, &x, &y);
    if (x < 0)
      break;
    ans = max (ans, x - f);
    f = y;
  }
  return ans;
}





// Coded by Z..

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