제출 #616039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
616039		chirathnirodha	커다란 상품 (IOI17_prize)	C++17	0 / 100	5 ms	2468 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define P push 
#define I insert 
#define F first 
#define S second

vector<pair<int,int> > v;
int sum[200000];
void query(int i){
	vector<int> tv=ask(i);
	v[i]={tv[0],tv[1]};
	sum[i]=v[i].F+v[i].S;
	return;
}
int find_best(int n) {
	int lol=0;
	for(int i=0;i<n;i++)v.PB(MP(-1,-1));
	for(int i=0;i<500;i++){
		query(i);
		if(sum[i]==0)return i;
		lol=max(lol,sum[i]);
	}
	for(int i=0;i<n;i++){
		if(v[i].F==-1)query(i);

		if(sum[i]==0)return i;
		if(sum[i]!=lol)continue;

		int l=i,r=n-1;
		while(l<=r){
			int m=(l+r)/2;
			if(v[m].F==-1)query(m);
			if(sum[m]==0)return i;
			if(v[m]==v[i]){
				l=m+1;
				i=m;
			}
			else r=m-1;
		}
	}
	return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80