Submission #114060

#	Time	Username	Problem	Language	Result	Execution time	Memory
114060		keko37	Gap (APIO16_gap)	C++14	100 / 100	89 ms	3728 KiB

gap

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

using namespace std;

typedef long long llint;

const llint INF = 1000000000000000007LL;

/*const int MAXN = 100005;

int nn, gmn, gmx, cnt;
llint a[MAXN];

void MinMax (llint s, llint t) {
    cnt++;
    cout << "bla " << s << " " << t << endl;
    llint x = INF, y = 0;
    for (int i = 0; i<nn; i++) {
        if (s <= a[i] && a[i] <= t) {
            cnt++;
            x = min(x, a[i]);
            y = max(y, a[i]);
        }
    }
    gmn = x;
    gmx = y;
}*/

long long findGap (int t, int n) {
    if (t == 1) {
        llint mn = -1, mx = INF + 1;
        vector <llint> v;
        while (v.size() < n) {
            //MinMax(mn + 1, mx - 1); mn = gmn; mx = gmx;
            MinMax(mn + 1, mx - 1, &mn, &mx);
            v.push_back(mn);
            if (mx != mn) v.push_back(mx);
            if (mx == mn) break;
        }
        sort(v.begin(), v.end());
        llint sol = 0;
        for (int i = 0; i < n-1; i++) {
            sol = max(sol, v[i+1] - v[i]);
        }
        return sol;
    } else {
        llint mn, mx, sol = 0;
        //MinMax(0, INF); mn = gmn; mx = gmx;
        MinMax(0, INF, &mn, &mx);
        llint d = mx - mn;
        llint len = d / (n-1);
        llint prosli = mn;
        llint a = mn + 1, b = min(a + len, mx - 1);
        while (a < mx) {
            llint currmn, currmx;
            //MinMax(a, b); currmn = gmn; currmx = gmx;
            MinMax(a, b, &currmn, &currmx);
            if (currmn != -1) {
                llint val = currmn - prosli;
                sol = max(sol, val);
                prosli = currmx;
            }
            a = b + 1;
            b = min(a + len, mx - 1);
        }
        sol = max(sol, mx - prosli);
        return sol;
    }
}

/*int main () {
    cin >> nn;
    for (int i = 0; i<nn; i++) {
        cin >> a[i];
    }
    cout << findGap(2, nn) << endl;
    cout << cnt;
    return 0;
}
*/

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:34:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (v.size() < n) {
                ~~~~~~~~~^~~

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