oj.uz

Submission #987047

# Submission time Handle Problem Language Result Execution time Memory
987047 2024-05-21T18:46:35 Z VMaksimoski008 The Big Prize (IOI17_prize) C++17
0 / 100
 2 ms 2136 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

pii memo[100005];

pii query(int p) {
	if(memo[p] != pii{ -1, -1 }) return memo[p];
	vector<int> res = ask(p);
	return memo[p] = { res[0], res[1] };
}

int sum(int p) { return query(p).first + query(p).second; }
int L(int p) { return query(p).first; }
int R(int p) { return query(p).second; }

int find_best(int n) {
	for(int i=0; i<n; i++) memo[i] = { -1, -1 };

	if(n <= 4500) {
		for(int i=0; i<n; i++)
			if(sum(i) == 0) return i;
	}
	
	int curr = -1, mx = 0;
	set<int> s;
	for(int i=0; i<min(900, n); i++) {
		mx = max(mx, sum(i));
		if(sum(i) == 0) return i;
	}

	//cout << "<> lollipop: " << mx << '\n';

	for(int i=1; i<=mx; i++) {
		int l=curr+1, r=n-1, pos=n-1;

		//cout << "it " << i << '\n';

		while(l <= r) {
			int mid = (l + r) / 2;
			//cout << mid << '\n';
			if(sum(mid) == 0) return mid;

			if(sum(mid) == mx) {
				if(L(mid) >= i) pos = mid, r = mid - 1;
				else l = mid + 1;
			} else {
				pos = mid;
				r = mid - 1;
			}
		}
		//cout << "found at: " << pos << '\n';

		curr = pos;
	}

	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1880 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 2136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -