oj.uz

Submission #102302

# Submission time Handle Problem Language Result Execution time Memory
102302 2019-03-24T09:17:26 Z bert30702 The Big Prize (IOI17_prize) C++17
20 / 100
 71 ms 880 KB 
#include <bits/stdc++.h>
#include "prize.h"
#define pii pair<int, int>
#define F first
#define S second
using namespace std;
unordered_map<int, pii> mp;
//vector<int> ask(int p) {
//	cout << p << endl;
//	int a, b; cin >> a >> b;
//	return {a, b};
//}
pii query(int p) {
	if(mp.find(p) != mp.end()) return mp[p];
	vector<int> v = ask(p);
	return mp[p] = {v[0], v[1]};
}
int find_best(int n) {
	int mx = 0;
	set<int> Yeee;
	for(int i = 0; i < min(n, 50); i ++) {
		int p = rand() % n;
		pii r = query(p);
		mx = max(mx, r.F + r.S);
	}
	// cout << mx << endl;
	vector<pair<int, pii> > OK;
	for(int i = 0; i < n; i ++) {
		pii p = query(i);
		// cout << " QQ " << i << ' ' << p.F << ' ' << p.S << endl;
		if(p.F + p.S == mx) {
			int l = i + 1, r = n;
			while(l != r) {
				int m = l + r >> 1;
				pii v = query(m);
				if(v.F == p.F and v.S == p.S) {
					i = m;
					l = i + 1, r = n;
				}
				else {
					r = m;
				}
			}
			if(l < n) {
				OK.push_back({l, query(l)});
				// cout << "INS " << l << endl;
			}
		}
		else {
			OK.push_back({i, p});
		}
	}
	// for(auto it: OK) cout << "OK " << it.F << endl;
	pii ans = {1 << 30, -1};
	// cout << OK.size() << endl;
	for(auto it: OK) ans = min(ans, {it.S.F + it.S.S, it.F});
	return ans.S;
}
//main () {
//	cout << find_best(7);
//}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 3 ms 396 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 2 ms 388 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 4 ms 256 KB Output is correct
10 Correct 4 ms 384 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 388 KB Output is correct
2 Correct 2 ms 392 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 388 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 4 ms 312 KB Output is correct
10 Correct 3 ms 256 KB Output is correct
11 Correct 23 ms 376 KB Output is correct
12 Correct 26 ms 376 KB Output is correct
13 Correct 24 ms 376 KB Output is correct
14 Partially correct 38 ms 540 KB Partially correct - number of queries: 5366
15 Incorrect 71 ms 880 KB Incorrect
16 Halted 0 ms 0 KB -