Submission #518271

#	Time	Username	Problem	Language	Result	Execution time	Memory
518271		Evirir	Gap (APIO16_gap)	C++17	100 / 100	60 ms	3340 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
ostream& operator<<(ostream &out, ii x){ out<<"("<<x.F<<","<<x.S<<")"; return out; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }
const ll INF = ll(1e18);
const int MOD = 998244353;

const bool DEBUG = 0;
const int MAXN = 100005;
const int LG = 21;

ll mn, mx;

void query(ll L, ll R)
{
    MinMax(L, R, &mn, &mx);
}

ll solve1(int n)
{
    ll a[n];
    mn=-1, mx=(ll)(1e18)+1;
    for(int l=0, r=n-1; l<=r; l++, r--)
    {
        query(mn + 1, mx - 1);
        a[l]=mn, a[r]=mx;
    }
    ll ans=0;
    forn(i,1,n) ans=max(ans, a[i]-a[i-1]);
    return ans;
}

ll solve2(int n)
{
    query(0, (ll)1e18);
    ll L=mn, R=mx;
    ll len=(R-L+n-2) / (n-1);

    vector<ll> v={mn};
    forn(i,0,n-1)
    {
        query(L+i*len+1, L+(i+1)*len);
        if(mn!=-1)
        {
            v.pb(mn); v.pb(mx);
        }
    }
    ll ans=0;
    forn(i,1,sz(v)) ans=max(ans, v[i]-v[i-1]);
    return ans;
}

long long findGap(int T, int N)
{
    return (T == 1 ? solve1(N)  : solve2(N));
}

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