| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 136001 | JustasZ | 커다란 상품 (IOI17_prize) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) cout << "[" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "]\n"
#define rd() abs((int)rng())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
/*vector<int> ask(int i)
{
cout << "? " << i << endl;
vector<int>a(2);
cin >> a[0] >> a[1];
return a;
}*/
int find_best(int n)
{
vector<int>a;
if(n < 5000)
{
for(int i = 0; i < n; i++)
{
a = ask(i);
if(a[0] == 0 && a[1] == 0)
return i;
}
}
int mx = 0;
for(int it = 0; it < 20; it++)
{
int p = rd() % n;
if(!mp.count(p))
mp[p] = ask(p);
a = mp[p];
mx = max(mx, a[0] + a[1]);
}
int cnt = 100;
int i = 0;
map<int, vector<int> >mp;
while(i < n)
{
//assert(++cnt < 10000);
if(!mp.count(i))
mp[i] = ask(i);
a = mp[i];
if(a[0] + a[1] == 0)
return i;
if(a[0] + a[1] == mx)
{
int fi = a[0], se = a[1];
int l = i + 1, r = n - 1;
while(l < r)
{
int mid = (l + r) / 2;
//assert(++cnt < 10000);
if(!mp.count(mid))
mp[mid] = ask(mid);
a = mp[mid];
if(a[0] + a[1] != mx)
r = mid;
else
{
if(a[0] > fi)
r = mid - 1;
else
l = mid + 1;
}
}
//assert(++cnt < 10000);
if(!mp.count(l))
mp[l] = ask(l);
a = mp[l];
assert(a[0] + a[1] != mx);
if(a[0] + a[1] == 0)
return l;
i = l + 1;
}
else
i++;
}
}