제출 #45409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45409		OneSubmissionMan	Gap (APIO16_gap)	C++11	100 / 100	113 ms	2232 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_1 ( 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;
}
ll solve_2 (int n) {
  ll F, S;
  MinMax (0ll, N, &F, &S);        
  ll len = max (1ll, ((S - F - 1 + n - 2) / (n - 1)));
  ll last = F;       
  ll ans = len;
  F++;    
  for (ll i = 1; i <= n; i++) {  
    ll x, y;                    
    MinMax (F + (i - 1) * len, F + i * len - 1, &x, &y);
    if (~x) { 
      ans = max (ans, x - last);
      last = y;
    }    
  }     
  return ans;                   
}
ll findGap (int t, int n) {  
  if (t == 1)
    return solve_1 (n);
  else
    return solve_2 (n);
}



// Coded by Z..

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