oj.uz

답안 #102308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102308 2019-03-24T09:32:52 Z bert30702 커다란 상품 (IOI17_prize) C++17
20 / 100
 72 ms 1204 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};
//}
int cnt = 0;
pii query(int p) {
	if(mp.find(p) != mp.end()) return mp[p];
	cnt ++;
	assert(cnt < 10000);
	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});
	assert(OK.size());
	return ans.S;
}
//main () {
//	cout << find_best(7);
//}

Compilation message

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

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 392 KB Output is correct
2 Correct 3 ms 408 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 2 ms 328 KB Output is correct
7 Correct 4 ms 324 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 256 KB Output is correct

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 304 KB Output is correct
3 Correct 3 ms 320 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 388 KB Output is correct
8 Correct 3 ms 388 KB Output is correct
9 Correct 2 ms 396 KB Output is correct
10 Correct 4 ms 256 KB Output is correct
11 Correct 19 ms 404 KB Output is correct
12 Correct 12 ms 488 KB Output is correct
13 Correct 24 ms 436 KB Output is correct
14 Partially correct 40 ms 504 KB Partially correct - number of queries: 5371
15 Runtime error 72 ms 1204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -