제출 #709268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
709268		WonderfulWhale	Gap (APIO16_gap)	C++17	30 / 100	51 ms	2648 KiB

gap

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

#define int long long
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

long long findGap(int32_t t, int32_t n) {
	if(t==1 || n<=10) {
		vector<int> a;
		vector<int> b;
		int l = 0;
		int r = 1e18;
		for(int i=0;i<(n+1)/2;i++) {
			int x, y;
			MinMax(l, r, &x, &y);
			a.pb(x);
			b.pb(y);
			l = x+1;
			r = y-1;
		}
		reverse(all(b));
		for(int x:b) a.pb(x);
		int ans = 0;
		for(int i=0;i<sz(a)-1;i++) {
			ans = max(ans, a[i+1]-a[i]);
		}
		return ans;
	}
	int l, r;
	MinMax(0, 1e18, &l, &r);
	int cur = l;
	int jump = 1;
	int ans = 0;
	while(cur!=r) {
		int x, y;
		MinMax(cur+1, cur+jump, &x, &y);
		if(x!=-1) {
			ans = max(ans, x-cur);
			cur = y;
		}
		jump*=2;
	}
	return ans;
}
			

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