oj.uz

Submission #245996

# Submission time Handle Problem Language Result Execution time Memory
245996 2020-07-08T00:08:53 Z rrrr10000 Gap (APIO16_gap) C++14
100 / 100
 78 ms 3308 KB 
#include <bits/stdc++.h>
#include"gap.h"
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
P ask(ll a,ll b){
    if(a>b)return P(-1,-1);
    ll m,n;
    MinMax(a,b,&m,&n);
    return P((ll)(m),(ll)(n));
}
ll findGap(int t,int n){
    if(t==1){
        vi v(n);
        ll a=0,b=1000000000000000000;
        rep(i,(n+1)/2){
            auto p=ask(a,b);
            v[i]=p.fi;v[n-i-1]=p.se;
            a=p.fi+1,b=p.se-1;
        }
        ll ans=0;
        rep(i,n-1)chmax(ans,v[i+1]-v[i]);
        return ans;
    }
    auto p=ask(0,1e18);
    ll a=p.fi,b=p.se;
    vi v;
    v.pb(a);
    ll k=(b-a+n-2)/(n-1);
    rep(i,n-1){
        auto p=ask(a+1+i*k,min(b-1,a+(i+1)*k));
        if(p.fi!=-1){
            v.pb(p.fi);v.pb(p.se);
        }
    }
    v.pb(b);
    ll ans=0;
    rep(i,v.size()-1)chmax(ans,v[i+1]-v[i]);
    return ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 18 ms 768 KB Output is correct
17 Correct 16 ms 768 KB Output is correct
18 Correct 17 ms 768 KB Output is correct
19 Correct 17 ms 768 KB Output is correct
20 Correct 14 ms 768 KB Output is correct
21 Correct 54 ms 1912 KB Output is correct
22 Correct 54 ms 1912 KB Output is correct
23 Correct 52 ms 1848 KB Output is correct
24 Correct 52 ms 1912 KB Output is correct
25 Correct 45 ms 1872 KB Output is correct
26 Correct 55 ms 1864 KB Output is correct
27 Correct 56 ms 1912 KB Output is correct
28 Correct 53 ms 1940 KB Output is correct
29 Correct 54 ms 1912 KB Output is correct
30 Correct 39 ms 1908 KB Output is correct
31 Correct 4 ms 384 KB Output is correct
32 Correct 4 ms 384 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 21 ms 896 KB Output is correct
17 Correct 23 ms 896 KB Output is correct
18 Correct 20 ms 1024 KB Output is correct
19 Correct 20 ms 896 KB Output is correct
20 Correct 11 ms 640 KB Output is correct
21 Correct 69 ms 2288 KB Output is correct
22 Correct 71 ms 2288 KB Output is correct
23 Correct 71 ms 2288 KB Output is correct
24 Correct 70 ms 2336 KB Output is correct
25 Correct 78 ms 3308 KB Output is correct
26 Correct 71 ms 2288 KB Output is correct
27 Correct 70 ms 2288 KB Output is correct
28 Correct 70 ms 2432 KB Output is correct
29 Correct 70 ms 2272 KB Output is correct
30 Correct 37 ms 1528 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct