# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
138553 | rajarshi_basu | 커다란 상품 (IOI17_prize) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <functional>
#include "prize.h"
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define vv vector
#define ii pair<int,int>
using namespace std;
const int MAXN = 2e5 + 1;
const ll INF = 1e17;
bool sp[MAXN];
int ans = -1;
struct DSU{
int parent[MAXN];
void init(){
FOR(i,MAXN)parent[i] =i;
}
int find(a){
if(a != parent[a])parent[a] = find(parent[a]);
return parent[a];
}
void merge(int a,int b){
if(!isSame(a,b)){
int pa = find(a);
int pb = find(b);
parent[pa] = pb;
}
}
bool isSame(int a,int b){
return find(a) == find(b);
}
} dsu;
int brute(int n){
FOR(i,n){
vi a = ask(i);
if(a[0] == 0 and a[1] == 0)return i;
}
}
int mx = 0;
void binsrch(int l,int r,int sp_left,int sp_right){
if(l > r)return;
if(ans != -1)return;
if(sp_right + sp_left == mx)return;
int mid = (l+r)/2;
vi a = ask(mid);
if(a[0] + a[1] == mx){
// this is a lollipop;
binsrch(l,mid-1,sp_left,a[1]);
binsrch(mid+1,r,a[0],sp_right);
}else{
// now we extend the pointers to both directions to find the closest lollipops
if(sp[0] + sp[1] == 0){
ans = mid;
return;
}
int rptr = mid+1;
vi a1;
while(rptr <= r){
a1 = ask(rptr);
if(a1[0] + a1[1] == 0){
ans = rptr;
return;
}else if(a1[0] + a[1] == mx){
binsrch(rptr+1,r,a[0],sp_right);
break;
}else{
rptr++;
}
}
int lptr = mid-1;
while(lptr >= l){
a1 = ask(lptr);
if(a1[0] + a[1] == 0){
ans = lptr;
return;
}else if(a[0] + a[1] == mx){
binsrch(l,lptr-1,sp_left,a[1]);
break;
}else{
lptr--;
}
}
}
}
int find_best(int n){
if(n <= 5000)return brute(n);
FOR(i,500){
int* a = ask(i);
mx = max(a[0]+a[1],mx);
}
binsrch(0,n-1,0,0);
return ans;
}