Submission #152924

#	Time	Username	Problem	Language	Result	Execution time	Memory
152924		arnold518	Gap (APIO16_gap)	C++14	100 / 100	76 ms	3308 KiB

gap

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int T, N;
ll A[MAXN+10], ans;

ll findGap(int _T, int _N)
{
    int i, j;
    T=_T; N=_N;

    if(T==1)
    {
        ll s=0, t=1e18;
        for(i=1, j=N; i<=j; i++, j--)
        {
            ll a, b;
            MinMax(s, t, &a, &b);
            A[i]=a; A[j]=b;
            s=a+1; t=b-1;
        }
        for(i=2; i<=N; i++) ans=max(ans, A[i]-A[i-1]);
        return ans;
    }
    else
    {
        ll s, e;
        MinMax(0, 1e18, &s, &e);
        if(N==2) return e-s;
        ll g=(e-s+N-2)/(ll)(N-1);
        ll a, b, p=s, q=s+g;
        vector<pll> V;
        while(1)
        {
            if(p>e) break;
            if(p>q) break;
            MinMax(p, q, &a, &b);
            if(a!=-1) V.push_back({a, b});
            p=q+1; q=p+g;
            q=min(q, e);
        }
        //for(i=0; i<V.size(); i++) printf("%lld %lld\n", V[i].first, V[i].second);
        for(i=1; i<V.size(); i++) ans=max(ans, V[i].first-V[i-1].second);
        return ans;
    }
}

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=1; i<V.size(); i++) ans=max(ans, V[i].first-V[i-1].second);
                  ~^~~~~~~~~

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