| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 390574 | faresbasbs | 커다란 상품 (IOI17_prize) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
vector<vector<int>> p[200001];
vector<int> ask(int pos){
if(p[pos].size()){
return p[pos];
}
return p[pos] = ask(pos);
}
int find_best(int n){
int sum = 0;
for(int i = 0 ; i < 450 ; i += 1){
int a = rand()%n;
vector<int> v = askk(a);
sum = max(sum,v[0]+v[1]);
if(v[0]+v[1] == 0){
return a;
}
}
vector<pair<int,vector<int>>> v;
int p = 0;
while(p < n){
while(p < n){
vector<int> f = askk(p);
if(f[0]+f[1] == sum){
v.push_back({p,f});
break;
}else{
if(f[0]+f[1] == 0){
return p;
}
p += 1;
}
}
p += 450;
}
v.push_back({n,{sum,0}});
for(int i = 0 ; i+1 < v.size() ; i += 1){
while(v[i+1].second[0] != v[i].second[0]){
int first = v[i].first , last = v[i+1].first;
while(last-first > 1){
int mid = (first+last)/2;
vector<int> f = askk(mid);
if(f[0]+f[1] == 0){
return mid;
}
if(f[0]+f[1] == sum && f[0] == v[i].second[0]){
first = mid;
}else{
last = mid;
}
}
vector<int> f;
for(int j = first+2 ; j < n ; j += 1){
f = askk(j);
if(f[0]+f[1] == 0){
return j;
}
if(f[0]+f[1] == sum){
v[i] = {j,f};
break;
}
}
}
}
}
/*int main(){
cout << find_best(8) << endl;
}*/