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 "gap.h"
#include <bits/stdc++.h>
using namespace std ;
#define ll long long
const int inf = 1e18 ;
ll findGap(int T , int n){
if ( T == 1 ){
vector <ll> vec ;
ll l = 1 , r = 1e18 , mn , mx , ans = 0 ;
while ( l <= r ){
if ( vec.size() == n ) break ;
MinMax( l , r , &mn , &mx ) ;
if ( mn == -1 || mx == -1 ) break ;
vec.push_back(mn) ;
if ( mn != mx ) vec.push_back(mx) ;
l = mn + 1 , r = mx-1 ;
}
sort ( vec.begin() , vec.end() ) ;
for ( int i = 1 ; i < n ; i ++ ) ans = max ( ans , vec[i]-vec[i-1] ) ;
return ans ;
}
ll l = 1 , r = 1e18 , x , y, ans = 0 , rr ;
MinMax( l , r , &x , &y ) ;
if ( n == 2 ) return abs(x-y) ;
rr = y ;
ll len = (y-x-1)/(n-1) ;
l = x , r = y ;
MinMax( x+1 , x+len+((y-x-1)%(n-1)) , &l , &r ) ;
if ( l != -1 ) ans = max ( ans , abs(x-l) ) ;
x += len+((y-x-1)%(n-1)) ; y = r ;
for ( ll i = 1 ; i < n-1 ; i ++ ){
MinMax( x+1 , x+len , &l , &r ) ;
x += len ;
if ( l == -1 ) continue ;
ans = max ( ans , abs( y-l ) ) ;
y = r ;
}
ans = max ( ans , abs(y-rr) ) ;
return ans ;
}
Compilation message (stderr)
gap.cpp:5:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
5 | const int inf = 1e18 ;
| ^~~~
gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:12:29: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
12 | if ( vec.size() == n ) break ;
| ~~~~~~~~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |