| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 242506 | WhaleVomit | Gap (APIO16_gap) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
#define MOO(i, a, b) for(int i=a; i<b; i++)
#define M00(i, a) for(int i=0; i<a; i++)
#define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--)
#define M00d(i,a) for(int i = (a)-1; i>=0; i--)
#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _ << " _ " <<
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;
/*vector<ll> vals;
ll m1 = 0;
ll m2 = 0;
void MinMax(ll s, ll t, ll& mn, ll& mx) {
m1++;
mn = (1e18)+1; mx = -1;
for(ll x: vals) {
if(s <= x && x <= t) {
mn = min(mn, x);
mx = max(mx, x);
m2++;
}
}
if(mx == -1) {
mn = -1;
}
}*/
pair<ll,ll> getMinMax(ll s, ll t) {
ll mn, mx;
MinMax(s, t, mn, mx);
return mp(mn, mx);
}
ll findGap(int t, int n) {
if(t == 1) {
vector<ll> nums;
ll lo = 0;
ll hi = 1e18;
int cnt = 0;
while(cnt < n) {
pair<ll,ll> p = getMinMax(lo, hi);
if(p.f == p.s) cnt++;
else cnt += 2;
nums.pb(p.f);
nums.pb(p.s);
lo = p.f+1;
hi = p.s-1;
}
sort(all(nums));
ll res = 0;
M00(i, n-1) {
res = max(res, nums[i+1] - nums[i]);
}
return res;
} else {
pair<ll,ll> p = getMinMax(0, 1e18);
ll small = p.f;
ll big = p.s;
ll cnt = big-small;
if(cnt < n) return 1;
ll blockcnt = n;
ll a = cnt/n;
ll b = a+1;
ll bcnt = cnt - a*n;
ll acnt = blockcnt - bcnt;
vector<pair<ll,ll>> blocks(blockcnt);
ll cur = small+1;
int numAs = 0;
M00(i, blockcnt) {
if(numAs < acnt) {
blocks[i] = mp(cur, cur+a-1);
cur += a;
numAs++;
} else {
blocks[i] = mp(cur, cur+b-1);
cur += b;
}
}
vector<pair<ll,ll>> answers(blockcnt);
M00(i, blockcnt) answers[i] = getMinMax(blocks[i].f, blocks[i].s);
ll res = 0;
ll last = small;
M00(i, blockcnt) {
if(answers[i].f != -1) {
res = max(res, answers[i].f - last);
last = answers[i].s;
}
}
return res;
}
}
/*bool test(vector<ll> v) {
vals = v;
ll ans = 0;
M00(i, sz(v)-1) {
ans = max(ans, v[i+1]-v[i]);
}
m1 = 0;
ll ans1 = findGap(1, sz(v));
if(2*m1 > sz(v)+1 || ans1 != ans) return 0;
m2 = 0;
ll ans2 = findGap(2, sz(v));
if(m2 > 3*sz(v) || ans2 != ans) return 0;
return 1;
}
int main() { FAST
vector<ll> v;
v.pb(2); v.pb(3); v.pb(6); v.pb(8);
if(test(v)) cout << "OK\n";
else cout << "BAD\n";
v.clear();
v.pb(0); v.pb(1);
if(test(v)) cout << "OK\n";
else cout << "BAD\n";
v.clear();
v.pb(1); v.pb(3); v.pb(7); v.pb(9); v.pb(11);
if(test(v)) cout << "OK\n";
else cout << "BAD\n";
}
*/