Submission #499598

#	Time	Username	Problem	Language	Result	Execution time	Memory
499598		iliccmarko	Gap (APIO16_gap)	C++14	100 / 100	62 ms	3220 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 10000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define single_case solve();
#define line cerr<<"----------"<<endl;
#define ios { /*ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL);*/ }
#define mod 1000000007LL
/*
void MinMax(ll l, ll r, ll *mini, ll *maks)
{
    cout<<l<<' '<<r<<endl;
    ll x;
    cin>>x;
    *mini = x;
    cin>>x;
    *maks = x;
}
*/
ll findGap(int t, int n)
{
    if(t==1LL)
    {
        deque<ll> dq;
        vector<pair<ll, ll> > v;
        ll l = 1LL;
        ll r = (ll)1e18;
        for(int i = 1;i<=(n+1)/2;i++)
        {
            ll mini, maks;
            MinMax(l, r, &mini, &maks);
            v.pb(make_pair(mini, maks));
            l = mini + 1;
            r = maks - 1;
        }
        for(int i = (n+1)/2-1;i>=0;i--)
        {
            if(v[i].first!=v[i].second)
            {
                dq.pb(v[i].second);
                dq.push_front(v[i].first);
            }
            else
            {
                dq.pb(v[i].first);
            }
        }
        ll maks = 1;
        for(int i = 1;i<len(dq);i++)
        {
            maks = max(maks, dq[i] - dq[i-1]);
        }
        return maks;
    }
    else
    {
        ll l, r, ans, mini, maks;
        l = 1LL;
        r = 1e18;
        MinMax(l, r, &mini, &maks);
        if(n==2)
        {
            return maks - mini;
        }
        vector<pair<ll, ll> > v;
        v.pb(make_pair(mini, mini));
        l = mini + 1;
        r = maks - 1;
        ll o = maks;
        ll d = (r-l+1)/((ll)n-2LL);
        ll rem = (r-l+1)%((ll)n-2LL);
        for(int i = 0;i<n-2;i++)
        {
            ll w = d;
            if(i<rem) w++;
            MinMax(l, l + w - 1LL, &mini, &maks);
            if(mini!=-1) v.pb(make_pair(mini, maks));
            l += w;
        }
        v.pb(make_pair(o, o));
        ans = 1;
        for(int i = 1;i<len(v);i++)
        {
            ans = max(ans, v[i].first - v[i-1].second);
        }
        //cout<<ans<<endl;
        return ans;
    }
}

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