| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 162968 | HungAnhGoldIBO2020 | Gap (APIO16_gap) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "gap.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;
if(dum!=-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(int i=1;i<=(N+1)/2;i++){
assert(min1+1<=max1-1);
MinMax(min1+1,max1-1,&min1,&max1);
assert(min1!=-1&&max1!=-1);
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;
}
}