제출 #705086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
705086		Abrar_Al_Samit	The Big Prize (IOI17_prize)	C++17	20 / 100	79 ms	344 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
using namespace std;

int find_best(int n) {

	int sq = min(n, (int)sqrt(n) + 10);
	int mx = -1, id;
	vector<int>prv;
	for(int i=0; i<sq; ++i) {
		auto v = ask(i);
		if(v[0]+v[1]>mx) {
			mx = v[0] + v[1];
			id = i;
			prv = v;
		}
	}
	vector<int>good;
	for(int i=0; i<id; ++i) {
		good.push_back(i);
	}

	while(id<n-1) {
		int to = min(n-1, id+sq);
		auto cr = ask(to);
		if(cr[0]==prv[0] && cr[1]==prv[1]) {
			id = to;
			continue;
		}
		int l = 0, r = to-id;
		while(l<r) {
			int mid = (l+r+1)/2;
			cr = ask(id+mid);
			if(cr[0]==prv[0] && cr[1]==prv[1]) {
				l = mid;
			} else {
				r = mid-1;
			}
		
		}
		id += l+1;
		while(id<n) {
			cr = ask(id);
			if(cr[0]+cr[1]==mx) {
				prv = cr;
				break;
			}
			good.push_back(id);
			++id;
		}
	}

	for(int x : good) {
		auto y = ask(x);
		if(y[0]+y[1]==0) {
			return x;
		}
	}
	assert(false);
}

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