| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 499596 | iliccmarko | Gap (APIO16_gap) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
MinMax(1, 1e18, &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 - 1, 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);
}
return ans;
}
}