Submission #671098

#	Time	Username	Problem	Language	Result	Execution time	Memory
671098		AdamGS	Gap (APIO16_gap)	C++17	100 / 100	56 ms	2632 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18;
ll findGap(int t, int n) {
        if(t==2) {
                ll mi, ma;
                MinMax(0, INF, &mi, &ma);
                ll x=(ma-mi+n-2)/(n-1), ans=x;
                ll lst=mi;
                for(ll i=mi; i<=ma; i+=x+1) {
                        ll a, b;
                        MinMax(i, i+x, &a, &b);
                        if(a==-1) continue;
                        ans=max(ans, a-lst);
                        lst=b;
                }
                return ans;
        }
        vector<ll>A, B;
        ll mi=0, ma=INF;
        rep(i, (n+1)/2)  {
                ll a, b;
                MinMax(mi, ma, &a, &b);
                if(a==-1) break;
                A.pb(a);
                B.pb(b);
                mi=a+1;
                ma=b-1;
        }
        reverse(all(B));
        for(auto i : B) A.pb(i);
        ll ans=0;
        rep(i, A.size()-1) ans=max(ans, A[i+1]-A[i]);
        return ans;
}

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
gap.cpp:38:9: note: in expansion of macro 'rep'
   38 |         rep(i, A.size()-1) ans=max(ans, A[i+1]-A[i]);
      |         ^~~

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