Submission #1015178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015178		vjudge1	Gap (APIO16_gap)	C++17	46.81 / 100	57 ms	7020 KiB

gap

#include <bits/stdc++.h>
// #include "grader.cpp"
#include "gap.h"

using namespace std;

typedef long long ll;
set<ll> st;
void recur(ll l, ll r){
    if (r < l) return ;
    if (r - l <= 1){
        MinMax(l, r, &l, &r);
        if (l != -1){
            st.insert(l);
            st.insert(r);
        }
        return ;
    }

    ll mid = (l + r) / 2;
    
    ll mn, mx;
    MinMax(l, mid, &mn, &mx);

    if (mn != -1){
        st.insert(mn);
        st.insert(mx);
        recur(mn + 1, mx - 1);
    }

    MinMax(mid + 1, r, &mn, &mx);
    if (mn != -1){
        st.insert(mn);
        st.insert(mx);
        recur(mn + 1, mx - 1);
    }
}

ll findGap(int T, int N){
    if (T == 1){
        ll mn = 0, mx = 1e18;
        while (N > 0){
            N -= 2;

            MinMax(mn, mx, &mn, &mx);

            st.insert(mn);
            st.insert(mx);
            
            mn++;
            mx--;
        }
    }
    else{
        recur(0, 1e18);
    }

    vector<ll> vec;
        for (ll x : st)
            vec.push_back(x);

    ll res = 0;
    for (ll i = 1; i < vec.size(); i ++)
        res = max(res, vec[i] - vec[i - 1]);
    return res;
}

Compilation message (stderr)

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

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