| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1113502 | epicci23 | 커다란 상품 (IOI17_prize) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#include "prize.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){
return l + rng() % (r-l+1);
}
int suf = -1;
vector<int> Cache={-1,-1};
map<int,vector<int>> dp;
vector<int> Ask(int i){
if( dp.count(i) ) return dp[i];
return dp[i] = ask(i);
}
int ask_all(int l,int r){
for(int i = l; i <= r; i++){
vector<int> x = Ask(i);
if(x[0] + x[1] == 0) return i;
if(x[1] == suf) Cache = x;
else suf--;
}
return -23;
}
int Learn(int l,int r){
if(l>r) return -1;
if(l==r){
auto u = Ask(l);
if(u[0] + u[1] == 0) return l;
if(u[1] == suf) Cache=u;
else suf--;
return -1;
}
auto X = Ask(r);
if(X[0] + X[1] == 0) return r;
if(X[1] == suf) return -1;
int mid = rng(l , r);
auto u = Ask(mid);
if(u[0] + u[1] == 0) return mid;
if(u[1] == suf) return Learn(mid + 1,r - 1);
int lf = Learn(l,mid - 1);
if(lf != -1) return lf;
if(u[1]==suf) Cache=u;
else suf--;
if(X[1] == suf - ( Cache[0]+Cache[1] > X[0] + X[1] ) ) return -1;
int hm = Learn( mid + 1, r - 1 );
if(hm !=- 1) return hm;
if(X[1] == suf) Cache = X;
else suf--;
return -1;
}
int find_best(int n){
if(n <= 1000) return ask_all(0, n - 1);
int art = 0;
for(int i = 0; i <= 500; i++){
if(art == 5) return Learn(i, n - 1);
vector<int> x = Ask(i);
if(x[0] + x[1] == 0) return i;
if(x[0] + x[1] > Cache[0] + Cache[1]) art++;
if(x[0] + x[1] >= Cache[0] + Cache[1]){
Cache = x;
suf = Cache[1];
}
else suf--;
}
return Learn(501, n - 1 );
}