Submission #221383

#TimeUsernameProblemLanguageResultExecution timeMemory
221383zoooma13Gap (APIO16_gap)C++14
100 / 100
81 ms1968 KiB
#include "bits/stdc++.h" #include "gap.h" using namespace std; long long findGap(int T, int N){ if(N <= 8 || T == 1){ vector <long long> A(N); MinMax(0 ,1e18 ,&A[0] ,&A[N-1]); for(int i=1; i<(N+1)/2; i++) MinMax(A[i-1]+1 ,A[N-i]-1 ,&A[i] ,&A[N-i-1]); long long ret = 1; for(int i=1; i<N; i++) ret = max(ret ,A[i]-A[i-1]); return ret; } long long mx_dist = 1 ,s ,t; MinMax(0 ,1e18 ,&s ,&t); long long mn = s ,mx = t ,lst = s; long long d = (mx-mn)/(N-1) ,p = (mx-mn)%(N-1); vector <long long> rngs(N); rngs[0] = mn+1; for(int i=1; i<N; i++) rngs[i] = rngs[i-1] + d + (i < p); for(int i=0; i<N-1; i++){ MinMax(rngs[i] ,rngs[i+1]-1 ,&s ,&t); if(s != -1) mx_dist = max(mx_dist ,s-lst) ,lst = t; } return max(mx-lst ,mx_dist); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...