Submission #1146877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146877		LCJLY	Gap (APIO16_gap)	C++20	30 / 100	42 ms	3260 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

int findGap(int32_t t, int32_t n){
	
	if(t==1){
		int arr[n];
		int l=0;
		int r=1e18;
		for(int x=0;x<(n+1)/2;x++){
			MinMax(l,r,&arr[x],&arr[n-1-x]);
			l=arr[x]+1;
			r=arr[n-1-x]-1;
		}
		int best=0;
		for(int x=1;x<n;x++){
			best=max(best,arr[x]-arr[x-1]);
		}
		return best;
	}
	
	pii hold;
	MinMax(0,1e18,&hold.first,&hold.second);
	
	int len=(hold.second-hold.first-1)/n;
	int cur=hold.first+1;
	vector<pii>v;
	v.push_back({hold.first,hold.first});
	pii hold2;
	for(int x=0;x<n-3;x++){
		MinMax(cur,cur+len-1,&hold2.first,&hold2.second);
		cur+=len;
		v.push_back(hold2);
	}
	
	if(cur<=hold.second-1){
		MinMax(cur,hold.second-1,&hold2.first,&hold2.second);
		v.push_back(hold2);
	}
	
	v.push_back({hold.second,hold.second});
	
	int best=0;
	int lst=1e18;
	for(int x=0;x<(int)v.size();x++){
		if(v[x].first==-1) continue;
		best=max(best,v[x].second-v[x].first);
		best=max(best,v[x].first-lst);
		lst=v[x].second;
	}
	
	return best;
}

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