Submission #548128

#	Time	Username	Problem	Language	Result	Execution time	Memory
548128		joshjms	Gap (APIO16_gap)	C++14	100 / 100	68 ms	2272 KiB

gap

#include "gap.h"

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

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << "\n";

ll t, n, ans;
ll l, r, mn, mx, x;
vector <ll> vect;

ll T1() {
    l = 0, r = 1e18;
    while(vect.size() < n) {
        MinMax(l, r, &mn, &mx);
        vect.pb(mn);
        if(mn != mx) vect.pb(mx);
        l = mn + 1;
        r = mx - 1;
    }
    sort(vect.begin(), vect.end());
    for(int i = 0; i < vect.size() - 1; i++)
        ans = max(ans, vect[i + 1] - vect[i]);
	return ans;
}

ll T2() {
    MinMax(0, 1e18, &l, &r);
    x = (r - l + n) / (n - 1);
    for(; l <= r; l += x) {
        MinMax(l, l + x - 1, &mn, &mx);
        if(mn != -1) vect.pb(mn);
        if(mn != mx && mx != -1) vect.pb(mx);
    }
    sort(vect.begin(), vect.end());
    for(int i = 0; i < vect.size() - 1; i++)
        ans = max(ans, vect[i + 1] - vect[i]);
    return ans;
}

ll findGap(int T, int N) {
    t = T, n = N;
    if(t == 1) return T1();
    else return T2();
}

Compilation message (stderr)

gap.cpp: In function 'long long int T1()':
gap.cpp:19:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   19 |     while(vect.size() < n) {
      |           ~~~~~~~~~~~~^~~
gap.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = 0; i < vect.size() - 1; i++)
      |                    ~~^~~~~~~~~~~~~~~~~
gap.cpp:27:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   27 |     for(int i = 0; i < vect.size() - 1; i++)
      |     ^~~
gap.cpp:29:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   29 |  return ans;
      |  ^~~~~~
gap.cpp: In function 'long long int T2()':
gap.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0; i < vect.size() - 1; i++)
      |                    ~~^~~~~~~~~~~~~~~~~

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