Submission #710305

#	Time	Username	Problem	Language	Result	Execution time	Memory
710305		sharaelong	Gap (APIO16_gap)	C++17	100 / 100	60 ms	3180 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

ll findGap(int T, int n) {
    ll mn, mx;
    pair<ll, ll> range = { 0, 1000000000000000000ll };
    
    vector<ll> arr;
    if (T == 1) {
        for (int i=0; i<(n+1)/2; ++i) {
            MinMax(range.first, range.second, &mn, &mx);
            // cout << mn << ' ' << mx << endl;
            arr.push_back(mn);
            arr.push_back(mx);
            range = { mn+1, mx-1 };
        }
    } else {
        MinMax(range.first, range.second, &mn, &mx);
        arr.push_back(mn);
        arr.push_back(mx);

        ll d = (mx-mn-1) / (n-1);
        ll mn_cpy = mn, mx_cpy = mx;
        // cout << d << ' ' << mn << ' ' << mx << endl;
        for (int i=0; i<n-1; ++i) {
            // cout << mn_cpy+1 + (d+1)*i << ' ' << mn_cpy + (d+1)*(i+1) << endl;
            MinMax(mn_cpy+1 + (d+1)*i, mn_cpy + (d+1)*(i+1), &mn, &mx);
            if (mn != -1) {
                arr.push_back(mn);
                arr.push_back(mx);
            }
        }
    }
    
    sort(arr.begin(), arr.end());
    ll gap = 0;
    for (int i=0; i+1<arr.size(); ++i) gap = max(gap, arr[i+1]-arr[i]);
    // cout << endl;
    return gap;
}

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:26:25: warning: unused variable 'mx_cpy' [-Wunused-variable]
   26 |         ll mn_cpy = mn, mx_cpy = mx;
      |                         ^~~~~~
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=0; i+1<arr.size(); ++i) gap = max(gap, arr[i+1]-arr[i]);
      |                   ~~~^~~~~~~~~~~

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