oj.uz

답안 #113521

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
113521 2019-05-26T06:26:12 Z E869120 커다란 상품 (IOI17_prize) C++14
0 / 100
 56 ms 2084 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

int A[200009];

vector<int> find_next(vector<int> R) {
	int maxn = 0;
	for (int i = 0; i < 12; i++) {
		vector<int> P = ask(R[rand() % R.size()]);
		maxn = max(maxn, P[0] + P[1]);
	}
	
	int cx = 0; vector<int> T;
	while (true) {
		vector<int> P = ask(R[cx]);
		if (P[0] + P[1] != maxn) { T.push_back(R[cx]); cx++; continue; }
		if (cx + 1 == (int)R.size()) break;
		
		int cl = cx, cr = R.size(), cm, maxn = -1;
		for (int i = 0; i < 20; i++) {
			cm = (cl + cr) / 2;
			vector<int> Q = ask(R[cm]);
			if (P == Q) { cl = cm; maxn = max(maxn, cm); }
			else { cr = cm; }
		}
		if (maxn == (int)R.size() - 1) break;
		T.push_back(R[maxn + 1]);
		cx = maxn + 2;
	}
	return T;
}

int find_best(int n) {
	vector<int> E; for (int i = 0; i < n; i++) E.push_back(i);
	while (E.size() >= 2) E = find_next(E);
	return E[0];
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2028 KB Output is correct
2 Correct 5 ms 1900 KB Output is correct
3 Correct 4 ms 1908 KB Output is correct
4 Incorrect 41 ms 2084 KB Incorrect
5 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1900 KB Output is correct
2 Correct 4 ms 2036 KB Output is correct
3 Correct 4 ms 2036 KB Output is correct
4 Incorrect 56 ms 1968 KB Incorrect
5 Halted 0 ms 0 KB -