Submission #744815

#	Time	Username	Problem	Language	Result	Execution time	Memory
744815		Cutebol	Gap (APIO16_gap)	C++17	30 / 100	73 ms	2256 KiB

gap

#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-3+n)/(n-1) ;
    l = x , r = y ;
    MinMax( x+1 , x+len , &l , &r ) ;
//    cout << x+1 << ' ' << x+len << endl ;
    if ( l != -1 ) ans = max ( ans , abs(x-l) ) ;
    x += len ; 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 ;
      |                  ~~~~~~~~~~~^~~~

• Subtask 1: 30 / 30
• Subtask 2: 0 / 70