oj.uz

Submission #72625

# Submission time Handle Problem Language Result Execution time Memory
72625 2018-08-26T12:38:47 Z mhnd The Big Prize (IOI17_prize) C++14
0 / 100
 127 ms 10432 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 10404 KB answer is not correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 10432 KB answer is not correct
2 Halted 0 ms 0 KB -