Submission #1076760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076760		miguel_tp	Gap (APIO16_gap)	C++17	0 / 100	3072 ms	1976 KiB

gap

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

using namespace std;

vector<long long> arr;

long long part1(int N)
{
    long long mn = -1, mx = 1e18 + 2;
    arr.resize(N);
    int i = 0, j = N-1;
    while(i <= j)
    {
        long long a = mn+1, b = mx-1;
        if(a > b)
            break;
        MinMax(a, b, &mn, &mx);

        arr[i] = mn;
        arr[j] = mx;
        i++;
        j--;
    }

    long long max_diff = 0;
    for(int i = 0; i < N-1; i++)
        max_diff = max(max_diff, arr[i+1] - arr[i]);

    return max_diff;
}

int idx = 0;

void aux(long long l, long long r, long long step)
{
    long long mn = -1, mx = 1e18 + 2;
    int i = 1;
    while(l + step * i - 1 < r)
    {
        MinMax(l + step * (i-1), l + step * i - 1, &mn, &mx);
        if(mn != -1) {
            if(step == 1) {
                arr[idx] = mn;
                idx++;
            }
            else
                aux(l + step * (i-1), l + step * i - 1, step / 1e6);
        }
        i++;
    }
}


long long part2(int N)
{
    arr.resize(N);
    aux(0, 1e18, 1e12);

    long long max_diff = 0;
    for(int i = 0; i < N-1; i++)
        max_diff = max(max_diff, arr[i+1] - arr[i]);

    return max_diff;
}


long long findGap(int T, int N)
{
    if(T == 1)
        return part1(N);
    else
        return part2(N);
}

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