Submission #1325859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325859		mopsyarka	Gap (APIO16_gap)	C++20	8.73 / 100	40 ms	1200 KiB

gap

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

#define ll long long
#define ull unsigned ll
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))
#define sz(x) (ll)(x.size())
#define pii pair < int, int >
#define pll pair < ll, ll >

#define debug(x) cerr << (#x) << " = " << (x) << endl

const int mod = 1e9 + 7;
const int N = 1001;
const ll OO = 1e18;

template<typename T>
bool umn (T &fi, T se) { return fi > se ? (fi = se, 1) : 0; }

template<typename T>
bool umx (T &fi, T se) { return fi < se ? (fi = se, 1) : 0; }

//vector < int > res = {2, 3, 6, 8};
//
//void MinMax (ll s, ll t, ll &mn, ll &mx) {
//    mn = mx = -1;
//    for (int i = 0; i < sz(res); ++i) {
//        if (res[i] >= s && res[i] <= t) {
//            if (mn == -1) mn = res[i];
//            mx = res[i];
//        }
//    }
//}

ll findGap (int t, int n) {
    ll a, b, mn, mx;
    MinMax(0, OO, &mn, &mx);
    ll s = 1;
    ll c = mn, e = mx;

    while (c < e) {
        while (1) {
            MinMax(c + 1, c + s, &mn, &mx);
            if (mn == -1) {
                MinMax(c + 1, c + s + s, &mn, &mx);
                if (mn == -1)
                    s += s;
                else {
                    umx(s, mn - c);
                    c = mx;
                    break;
                }
            } else {
                umx(s, mn - c);
                c = mx;
                break;
            }
        }
    }
    return s;
}

//void slv () {
//    cout << findGap(1, sz(res));
//}
//
//signed main () {
//    ios_base::sync_with_stdio(false);
//    cin.tie(nullptr);
//    int test = 1;
////    cin >> test;
//    while (test--) {
//        slv();
//        cout << "\n";
//    }
//}

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