Submission #1109606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109606		dzhoz0	Gap (APIO16_gap)	C++17	30 / 100	46 ms	4108 KiB

gap

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

#define INF 1e18
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>
#define ll long long

pair<ll, ll> ask(ll l, ll r) {
    ll x, y;
    MinMax(l, r, &x, &y);
    // MinMax(l, r, x, y);
    return {x, y};
}

ll findGap(int T, int N)
{
    ll l = 1, r = 1e18;
    vector<ll> v;
    while(l <= r && v.size() < N) {
        // cout << l << ' ' << r << ": ";
        pair<ll, ll> ans = ask(l, r);
        // cout << ans.f << ' ' << ans.s << '\n';
        if(ans.f == -1) break;

        v.push_back(ans.f);
        if(ans.f != ans.s) v.push_back(ans.s);

        l = ans.f + 1;
        r = ans.s - 1;
    }
    sort(v.begin(), v.end());
    ll res = -INF;    
    for(int i = 1; i < N; i++) res = max(res, v[i] - v[i - 1]);


    return res;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:23:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |     while(l <= r && v.size() < N) {
      |                     ~~~~~~~~~^~~

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