Submission #593043

#	Time	Username	Problem	Language	Result	Execution time	Memory
593043		Tekor	The Big Prize (IOI17_prize)	C++17	20 / 100	102 ms	11032 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,int gr) {
	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] < gr)q.pb(mp(mid,resp[0] + resp[1]));
	int x = resp[0];
	int kk = min(gr,resp[0] + resp[1]);
	for(auto to : q) {
		if(to.f < mid && to.s < resp[0] + resp[1])x--;
	}
	if(x != 0) {
		int val = fin(L,mid - 1,kk);
		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,kk);
		return val;
	}
	return -1;
}
int find_best(int pp) {
	k = pp;
	int m = (k - 1) / 2;
	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,tt[0] + tt[1]);
		if(val != -1)return val;
	}
	int ff = fin(m + 1,k - 1,tt[0] + tt[1]);
	//assert(ff != -1);
	return ff;
}

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