제출 #1358191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358191		warrenn	커다란 상품 (IOI17_prize)	C++20	90 / 100	20 ms	11364 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5;
vector<int> isi[maxn+2];

vector<int>query(int idx){
	if(isi[idx][0]!=-1)return isi[idx]; 
	isi[idx]=ask(idx); 
	return isi[idx];
}

int sum(int idx){
	if(isi[idx][0]==-1)isi[idx]=ask(idx);
	return isi[idx][0]+isi[idx][1];
}

int find_best(int n) {
	for(int q=0;q<n;q++)isi[q]={-1,-1};
	isi[0]=query(0);
	if(sum(0)==0)return 0;
	
	int cur=0; 
	while(cur<n){
		query(cur);
		if(sum(cur)==0)return cur;
		if(sum(cur)<sum(0)){
			cur++; continue;
		}
		
		int l=cur+1,r=n-1,nxt=n;
		while(l<=r){
			int mid=(l+r)/2;
			query(mid);
			if(sum(mid)==0)return mid;
			if(isi[mid][1]==isi[cur][1]){
				l=mid+1;
			}
			else{
				nxt=mid; r=mid-1;
			}
		}
		
		cur=nxt;
	}
	return cur;
}

• 서브태스크 1: 20 / 20
• 서브태스크 2: 70 / 80