oj.uz

Submission #61542

# Submission time Handle Problem Language Result Execution time Memory
61542 2018-07-26T07:23:15 Z zadrga The Big Prize (IOI17_prize) C++14
0 / 100
 24 ms 5304 KB 
//  8.55  + 25min 


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

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1 << 30)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 201111
#define SQRT 450

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

int max_val;
int ans;
bool used[maxn];
vector<int> v[maxn];

vector<int> ASK(int x){
	if(!used[x]){
		v[x] = ask(x);
		used[x] = 1;
	}
	return v[x];
}

void solve(int L, int D){
	if(ans != -1 || L > D)
		return;

	int l = -1, d = -1;
	vector<int> left, right;
	for(int i = L; i <= D; i++){
		left = ASK(i);

		if(left[0] + left[1] == 0){
			ans = i;
			return;
		}

		if(left[0] + left[1] == max_val){
			l = i;
			break;
		}
	}

	if(l == -1)
		return;

	for(int i = D; i > l; i--){
		right = ASK(i);

		if(right[0] + right[1] == 0){
			ans = i;
			return;
		}

		if(right[0] + right[1] == max_val){
			d = i;
			break;
		}
	}
	if(d == -1)
		return;

	int num = left[1] - right[1];
	if(num == 0)
		return;

	int mid = (l + d) / 2;
	solve(l, mid);
	solve(mid + 1, d);
}

int find_best(int n){
	max_val = -1;
	for(int i = 0; i < min(2 * SQRT, n); i++){
		vector<int> ret = ASK(i);
		max_val = max(max_val, ret[0] + ret[1]);
	}

	ans = -1;
	for(int i = 0; i < SQRT; i++){
		int l = i * SQRT;
		solve(l, min(n, l + SQRT - 1));
	}
	return ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5136 KB Output is correct
2 Correct 24 ms 5176 KB Output is correct
3 Correct 21 ms 5276 KB Output is correct
4 Incorrect 23 ms 5304 KB Integer 200000 violates the range [0, 199999]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 5304 KB Integer 200000 violates the range [0, 199999]
2 Halted 0 ms 0 KB -