제출 #593816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
593816		AlperenT	커다란 상품 (IOI17_prize)	C++17	20 / 100	77 ms	344 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int int_rand(int a, int b){
	return uniform_int_distribution<int>(a, b)(rng);
}

const int TRYMAX = 10, K = 2000;

int maxcnt = 0;

int find_best(int n){
	for(int i = 0; i < TRYMAX; i++){
		vector<int> vec = ask(int_rand(0, n - 1));

		maxcnt = max(maxcnt, vec[0] + vec[1]);
	}

	vector<bool> ismax(n, false);

	int pos = 0, prefix = 0;

	while(pos < n){
		vector<int> vec = ask(pos);

		if(vec[0] + vec[1] != maxcnt){
			pos++;
			continue;
		}

		int l = pos - 1, r = min(pos + K, n);

		while(r - l > 1){
			int m = l + (r - l) / 2;

			vector<int> vec = ask(m);

			if(vec[0] + vec[1] == maxcnt && (m + 1 - vec[0]) - prefix == m - pos + 1) l = m;
			else r = m;
		}

		prefix += (l - pos + 1);

		for(int i = pos; i <= l; i++) ismax[i] = true;

		pos = max(pos + 1, l + 1);
	}

	for(int i = 0; i < n; i++){
		if(!ismax[i]){
			vector<int> vec = ask(i);

			if(vec[0] + vec[1] == 0) return i;
		}
	}

	return -1;
}

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