| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 226542 | bharat2002 | 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.
/*input
*/
#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 100;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl
//Trace prints the name of the variable and the value.
int arr[N];
/*int vals[N];int nc;
void MinMax(int l, int r, int &a, int &b)
{
for(int i=1;i<N;i++)
{
if(vals[i]>=l) {a=vals[i];break;}
}
for(int i=1;i<N;i++)
{
if(vals[i+1]>r||i==nc) {b=vals[i];return;}
}
}*/
int findGap(int t, int n)
{
if(t==1)
{
MinMax(0, 1e18, &arr[1], &arr[n]);
int i=2;
while(i<=n-i+1)
{
MinMax(arr[i-1] + 1, arr[n-i+2]-1, &arr[i], &arr[n-i+1]);i++;
}
int ans=-inf;
for(int j=1;j<n;j++) ans=max(ans, arr[j+1]-arr[j]);
return ans;
}
MinMax(0, 1e18, &arr[1], &arr[n]);
if(n==2) return arr[n]-arr[1];
int diff=(arr[n]-arr[1])/(n-1);
if((arr[n]-arr[1])%(n-1)!=0) diff++;
int ans=0;
int prevel=arr[1], curl=arr[1]+1, curr=arr[1]+1+diff;
while(curl<arr[n])
{
int cmin, cmax;MinMax(curl, curr, &cmin, &cmax);
if(cmin!=-1) ans=max(ans, cmin-prevel);
ans=max(ans, cmax - cmin);
if(cmax!=-1) prevel=cmax;
curl=curr + 1;curr=curl + diff;
}
return ans;
}
/*signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t, n;cin>>t>>n;nc=n;
for(int i=1;i<=n;i++) cin>>vals[i];
cout<<findGap(t, n);
}*/