oj.uz

Submission #102306

# Submission time Handle Problem Language Result Execution time Memory
102306 2019-03-24T09:29:07 Z bert30702 The Big Prize (IOI17_prize) C++17
20 / 100
 74 ms 632 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) {
	srand(time(0));
	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);
	}
	vector<pair<int, pii> > OK;
	for(int i = 0; i < n; i ++) {
		pii p = query(i);
		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)});
			}
		}
		else {
			OK.push_back({i, p});
		}
	}
	pii ans = {1 << 30, -1};
	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:33: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 3 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 2 ms 396 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 3 ms 396 KB Output is correct
6 Correct 3 ms 392 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 4 ms 396 KB Output is correct
9 Correct 2 ms 388 KB Output is correct
10 Correct 2 ms 324 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 4 ms 304 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 11 ms 488 KB Output is correct
12 Correct 29 ms 376 KB Output is correct
13 Correct 21 ms 376 KB Output is correct
14 Partially correct 30 ms 440 KB Partially correct - number of queries: 5369
15 Incorrect 74 ms 632 KB Incorrect
16 Halted 0 ms 0 KB -