oj.uz

Submission #1045205

# Submission time Handle Problem Language Result Execution time Memory
1045205 2024-08-05T18:58:00 Z beaconmc The Big Prize (IOI17_prize) C++14
20 / 100
 1000 ms 1516 KB 
#include "prize.h"

#include <bits/stdc++.h>
 
typedef int ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;


map<ll, vector<ll>> cache;

vector<ll> query(int n){

	if (cache.count(n)) return cache[n];
	else return cache[n] = ask(n);
}


int find_best(int n) {
	cache.clear();
	vector<ll> stuff(n);

	FOR(i,0,n) stuff[i] = i;
	ll maxi = -1;
	FOR(i,0,min(500, n)){
		vector<ll> sus = query(i);
		maxi = max(maxi, sus[0]+sus[1]);
	}
	

	vector<ll> found;

	ll ans = -1;


	while (ans == -1){


		ll lo = 0;
		ll hi = stuff.size()-1;
		bool skip = false;
		while (lo < hi){


			ll mid = (lo+hi)/2;

			vector<ll> sus = query(stuff[mid]);


			if (sus[0] + sus[1] < maxi){
					
				if (sus[0]+sus[1]==0) return stuff[mid];
				found.push_back(stuff[mid]);
				stuff.erase(stuff.begin()+mid);
				skip = true;
				break;
			}else{
				sort(found.begin(), found.end());
				ll idk = upper_bound(found.begin(), found.end(), stuff[mid]) - found.begin();
				if (idk < sus[0]){
					hi = mid-1;
				}else{
					lo = mid+1;
				}
			}
		}
		if (skip) continue;
		vector<ll> sus = query(lo);
		if (sus[0]+sus[1] == maxi) continue;
		if (sus[0]+sus[1]==0) return stuff[lo];
		found.push_back(stuff[lo]);
		stuff.erase(stuff.begin()+lo);

	}
	return 0;

}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1368 KB Output is correct
2 Correct 3 ms 1516 KB Output is correct
3 Correct 3 ms 1112 KB Output is correct
4 Correct 2 ms 1112 KB Output is correct
5 Correct 2 ms 1112 KB Output is correct
6 Correct 2 ms 1112 KB Output is correct
7 Correct 2 ms 1112 KB Output is correct
8 Correct 3 ms 1112 KB Output is correct
9 Correct 3 ms 1368 KB Output is correct
10 Correct 3 ms 1112 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1368 KB Output is correct
2 Correct 3 ms 1368 KB Output is correct
3 Correct 2 ms 1112 KB Output is correct
4 Correct 2 ms 1112 KB Output is correct
5 Correct 3 ms 1112 KB Output is correct
6 Correct 2 ms 1112 KB Output is correct
7 Correct 3 ms 1112 KB Output is correct
8 Correct 3 ms 1112 KB Output is correct
9 Correct 3 ms 1112 KB Output is correct
10 Correct 2 ms 1112 KB Output is correct
11 Execution timed out 3046 ms 1112 KB Time limit exceeded
12 Halted 0 ms 0 KB -