제출 #593041

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

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define en '\n'
const int N = 2e5 + 10;
int k,mx,kol;
vector <int> was[N];
bool u[N];
vector <pii> q; 
/*
8
3 2 3 1 3 3 2 3
*/
vector <int> Ask(int x) {
	if(u[x])return was[x];
	u[x] = 1;
	was[x] = ask(x);
	return was[x];
}
int fin(int L,int R) {
	if(L > R)return -1;
	int l = L,r = R;
	int mid = (l + r) / 2;
	//cout << l << " " << r << " " << mid << endl;
	kol++;
	assert(kol <= 10000);
	vector <int> resp = Ask(mid);
	if(resp[0] + resp[1] == 0)return mid;
	if(resp[0] + resp[1] != mx)q.pb(mp(mid,resp[0] + resp[1]));
	int x = resp[0];
	for(auto to : q) {
		if(to.f < mid && to.s > resp[0] + resp[1])x--;
	}
	if(x != 0) {
		int val = fin(L,mid - 1);
		if(val != -1)return val;
	}
	int y = resp[1];
	for(auto to : q) {
		if(to.f > mid && to.s > resp[0] + resp[1])y++;
	}
	if(y != 0) {
		int val = fin(mid + 1,R);
		return val;
	}
	return -1;
}
int find_best(int pp) {
	k = pp;
	int m = (k - 1) / 2;
	for(int i = 0;i < min(500,k);i++) {
		vector <int> rep = ask(i);
		mx = max(mx,rep[0] + rep[1]);
	}
//	mx = 3;
	//cout << k << " ";
	//cout << m << endl;
	kol++;
	vector <int> tt = Ask(m);
	if(tt[0] + tt[1] != mx)q.pb(mp(m,tt[0] + tt[1]));
	if(tt[0] + tt[1] == 0)return m;
	if(tt[0] != 0) {
		int val = fin(0,m - 1);
		if(val != -1)return val;
	}
	return fin(m + 1,k - 1);
}

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