제출 #122743

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122743		SirCeness	커다란 상품 (IOI17_prize)	C++14	20 / 100	89 ms	2728 KiB

prize

#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#include "prize.h"
using namespace std;
typedef long long ll;

int arr[200005];
int n;
int tmp[200005];
pair<int, int> anslar[200005];
int maxx;
int soncevap = -1;
// 22

vector<int> get(int k){
	//cout << "get(" << k << ")" << endl;
	vector<int> ans(2);
	if (anslar[k].first == -1){
		ans = ask(k);
		anslar[k] = mp(ans[0], ans[1]);
		if (ans[0] + ans[1] == 0) soncevap = k;
	}
	ans[0] = anslar[k].first;
	ans[1] = anslar[k].second;
	return ans;
}


int find_best(int size){
	n = size;
	for (int i = 0; i < size; i++) arr[i] = i;
	for (int i = 0; i < n; i++) anslar[i] = mp(-1, -1);
	
	srand(time(0));
	maxx = 0;
	for (int i = 0; i < min(50, n); i++){
		vector<int> ans = get(rand()%n);
		if(soncevap != -1) return soncevap;
		maxx = max(ans[0] + ans[1], maxx);
		if (maxx >= sqrt(sqrt(n))) break;
	}
	
	//cout << "maxx: " << maxx << endl;
	
	for (int i = 0; i < maxx; i++){
		//cout << "i: " << i << endl;
		int l = 0;
		int r = n-1;
		while (l < r){
			int m = (l+r+1)/2;
			vector<int> ans = get(m);
			if(soncevap != -1) return soncevap;
			while (ans[0] + ans[1] != maxx && l < m){
				m--;
				ans = get(m);
				if(soncevap != -1) return soncevap;
			}
			if (l == m) break;
			if (ans[0] > i) r = m-1;
			else l = m;
		}
		//cout << "find: " << l << endl;
		vector<int> ans = get(l);
		if(soncevap != -1) return soncevap;
		if (ans[0] + ans[1] == maxx) l++;
		if (l >= n) continue;
		while (anslar[l].first != -1 && l < n){
			if (anslar[l].first + anslar[l].second == maxx) break;
			l++;
		}
		if (l >= n) continue;
		ans = get(l);
		if(soncevap != -1) return soncevap;
		
	}
	
	//cout << "size: " << vec.size() << endl;
	assert(soncevap != -1);
	return soncevap;
}

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