Submission #680582

#	Time	Username	Problem	Language	Result	Execution time	Memory
680582		Alexandruabcde	Gap (APIO16_gap)	C++14	100 / 100	61 ms	3196 KiB

gap

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

using namespace std;

constexpr long long INF = 1LL * 1e18;
constexpr int NMAX = 1e5 + 2;

long long ans = 0;
long long A[NMAX];

void Solve_Task_1(int N) {
    long long st = 1, dr = INF;
    long long *Min, *Max;

    Min = A + 1;
    Max = A + N;

    for (int i = 2; i <= N; i += 2) {
        MinMax(st, dr, Min, Max);
        st = (*Min) + 1;
        dr = (*Max) - 1;
        Min++;
        Max--;
    }

    if (N % 2 == 1) {
        MinMax(st, dr, A + (N+1) / 2, A + (N+1)/2);
    }

    for (int i = 2; i <= N; ++ i )
        ans = max(ans, A[i] - A[i-1]);
}

void Solve_Task_2(int N) {
    ans = 0;
    long long st = 0, dr = INF;
    long long *Min, *Max;
    Min = A + 1;
    Max = A + 2;

    MinMax(st, dr, Min, Max);
    long long average_diff = (A[2] - A[1]) / (N - 1);
    dr = A[2];
    st = A[1];

    vector <long long> values;
    while (st <= dr) {
        MinMax(st, st + average_diff, Min, Max);

        if (A[1] != -1) values.push_back(A[1]);
        if (A[2] != -1) values.push_back(A[2]);

        st += average_diff + 1;
    }

    for (int i = 1; i < values.size(); ++ i )
        ans = max(ans, values[i] - values[i-1]);
}

long long findGap(int T, int N)
{
    ans = 0;
    if (T == 1) Solve_Task_1(N);
    else Solve_Task_2(N);

	return ans;
}

Compilation message (stderr)

gap.cpp: In function 'void Solve_Task_2(int)':
gap.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 1; i < values.size(); ++ i )
      |                     ~~^~~~~~~~~~~~~~~

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