Submission #591372

#	Time	Username	Problem	Language	Result	Execution time	Memory
591372		MohamedFaresNebili	Gap (APIO16_gap)	C++14	100 / 100	54 ms	3232 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
 
            using namespace std;
 
            using ll = long long;
            using ld = long double;
 
            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
 
            ll findGap(int T, int N) {
                if(T == 1) {
                    vector<ll> A(N + 2);
                    A[0] = -1ll, A[N + 1] = 1000000000ll * 1000000000ll + 1ll;
                    for(ll l = 1; l <= (N + 1) / 2; l++) {
                        MinMax(A[l - 1] + 1, A[N - l + 2] - 1, &A[l], &A[N - l + 1]);
                    }
                    ll res = 0;
                    for(ll l = 2; l <= N; l++)
                        res = max(res, A[l] - A[l - 1]);
                    return res;
                }
                vector<ll> S; ll mn = -1, mx = -1, res = 0;
                MinMax(0ll, 1000000000000000000ll, &mn, &mx);
                ll L = mn, R = mx; ll md = (R - L + N) / N;
                S.push_back(L);
                while(L < R) {
                    MinMax(L + 1, min(R - 1, L + md), &mn, &mx); L += md;
                    if(mn == -1 && mx == -1) continue;
                    S.push_back(mn); S.push_back(mx); 
                }
                S.push_back(R);
                for(int l = 1; l < S.size(); l++)
                    res = max(res, S[l] - S[l - 1]);
                return res;
            }

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:40:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |                 for(int l = 1; l < S.size(); l++)
      |                                ~~^~~~~~~~~~

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