제출 #1218798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218798		Captain_Georgia	Gap (APIO16_gap)	C++20	100 / 100	51 ms	2728 KiB

gap

#include "gap.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll findGap (int T, int N) {
  	if (T == 1 || N <= 2) {
    		vector<ll> A, B;
    		ll l = 0, r = 1e18;
    		while (l <= r && A.size() + B.size() < N) {
      			ll x, y; 
            MinMax(l, r, &x, &y);
      			if (x == -1) break;
      			A.emplace_back(x);
      			if (x < y) B.emplace_back(y);
      			l = x + 1, r = y - 1;
    		}
    		for (int i = B.size() - 1;i >= 0;i --) A.emplace_back(B[i]);
    		
    		ll ans = 0;
    		for (int i = 1;i < A.size();i ++) ans = max(ans, A[i] - A[i - 1]);
    		return ans;
  	}	
    ll l, r; 
    MinMax(0, 1e18, &l, &r);
    ll bl = (r - l) / (N - 1) + ((r - l) % (N - 1) != 0);
    ll ans = bl;
    for (ll i = l, pre = -1;i <= r;i += bl + 1) {
        ll x = i, y = i + bl, a, b;
        MinMax(x, y, &a, &b);
        if (a != -1) {
            if (pre != -1) ans = max(ans, a - pre);
            pre = b;
        }
    }
    return ans;
}

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