Submission #521143

#	Time	Username	Problem	Language	Result	Execution time	Memory
521143		Jomnoi	Gap (APIO16_gap)	C++17	100 / 100	59 ms	3192 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
#define DEBUG 0
using namespace std;

const long long INF = 1e18;

long long findGap(int T, int N) {
    vector <long long> a;
    if(T == 1) {
        a.resize(N);
        MinMax(0, INF, &a[0], &a[N - 1]);
        int l = 1, r = N - 2;
        while(l <= r) {
            MinMax(a[l - 1] + 1, a[r + 1] - 1, &a[l], &a[r]);
            l++;
            r--;
        }
    }
    else {
        long long L, R;
        MinMax(0, INF, &L, &R);
        long long minimum = (R - L + N - 2) / (N - 1);
        a.push_back(L);
        L++;
        while(L < R) {
            long long nL, nR;
            MinMax(L, min(L + minimum, R - 1), &nL, &nR);
            if(nL != -1 and nR != -1) {
                a.push_back(nL);
                a.push_back(nR);
            }

            L = min(L + minimum, R - 1) + 1;
        }
        a.push_back(R);
    }

    long long ans = 0;
    for(int i = 1; i < a.size(); i++) {
        ans = max(ans, a[i] - a[i - 1]);
    }
    return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:40:22: 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 i = 1; i < a.size(); i++) {
      |                    ~~^~~~~~~~~~

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