oj.uz

Submission #390543

# Submission time Handle Problem Language Result Execution time Memory
390543 2021-04-16T09:36:46 Z aarr The Big Prize (IOI17_prize) C++14
0 / 100
 2 ms 456 KB 
#include "prize.h"

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 200 * 1000 + 5;
pair <int, int> res[N];
bool mark[N];

void ask_save(int k) {
	if (!mark[k]) {
		vector <int> vec = ask(k);
		res[k].first = vec[0];
		res[k].second = vec[1];
	}
	
}

int solve(int s, int e) {
	if (e - s <= 2) {
		return n;
	}
	int md = (s + e) / 2;
	ask_save(md);
	if (res[md].first + res[md].second == 0) {
		return md;
	}
	int ans = n;
	if (res[md] != res[s]) {
		ans = solve(s, md + 1);
		if (ans < n) {
			return ans;
		}
	}
	if (res[md] != res[e]) {
		ans = min(ans, solve(md, e));
	}
	return ans;
}

int find_best(int n) {
	ask_save(0);
	ask_save(n - 1);
	if (res[0].first + res[0].second == 0) {
		return 0;
	}
	if (res[n - 1].first + res[n - 1].second == 0) {
		return n - 1;
	}
	return solve(0, n);
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 80.0

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