# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
162965 | HungAnhGoldIBO2020 | Gap (APIO16_gap) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const long long inf=1e18;
long long findGap(int T,long int N){
if(T==2){
long long min1,max1;
MinMax(0,inf,min1,max1);
long long num=max1-min1-1;
assert(num>=N-2);
long long val=num/(N-1),cnt=num%(N-1);
long long ans=val,now=min1+1,now1,dum,dum1;
vector<long long> ans_lis;
ans_lis.push_back(min1);
for(int i=1;i<N;i++){
now1=now+val-1;
if(cnt){
cnt--;
now1++;
}
if(now<=now1){
MinMax(now,now1,dum,dum1);
now=now1+1;
ans_lis.push_back(dum);
ans_lis.push_back(dum1);
}
}
ans_lis.push_back(max1);
for(int i=0;i<ans_lis.size()-1;i++){
ans=max(ans,ans_lis[i+1]-ans_lis[i]);
}
return ans;
}
else{
long long min1=-1,max1=inf+1,ans=0;
vector<long long> ans_lis,ans_lis1;
for(i=1;i<=(N+1)/2;i++){
assert(min1+1<=max1-1);
MinMax(min1+1,max1-1,min1,max1);
ans_lis.push_back(min1);
ans_lis1.push_back(max1);
}
while(ans_lis1.size()){
ans_lis.push_back(ans_lis1.back());
ans_lis1.pop_back();
}
for(int i=0;i+1<ans_lis.size();i++){
ans=max(ans,ans_lis[i+1]-ans_lis[i]);
}
return ans;
}
}