Submission #72625

#	Time	Username	Problem	Language	Result	Execution time	Memory
72625		mhnd	The Big Prize (IOI17_prize)	C++14	0 / 100	127 ms	10432 KiB

prize

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5+50;
const int oo = 1e9;
const int mod = 1e9+7;

int dsu[N];
vector<int> a;

int find(int u){
	return u==dsu[u]?u:dsu[u] = find(dsu[u]);
}

int find_best(int n){
	int cur = 0;
	set<int> st;
	for(int i=0;i<n;i++){
		dsu[i]=i;
		st.insert(i);
	}
	for(int i=0;i<5000;i++){
		a = ask(cur);
		if(!a[0] && !a[1])return cur;
		if(a[0] > a[1]){
			int md = cur/2;
			md = find(md);
			st.erase(md);
			auto it = st.lower_bound(md);
			if(it != st.begin())it--;
			dsu[md] = *it;
			cur = md;
		}else{
			int md = (n+cur-1)/2;
			md = find(md);
			st.erase(md);
			auto it = st.lower_bound(md);
			if(it != st.begin())it--;
			dsu[md] = *it;
			cur = md;
		}
	}
	return 0;
}

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