Submission #113522

#	Time	Username	Problem	Language	Result	Execution time	Memory
113522		E869120	커다란 상품 (IOI17_prize)	C++14	20 / 100	82 ms	2192 KiB

prize

#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 (cx < R.size()) {
		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];
}

Compilation message (stderr)

prize.cpp: In function 'std::vector<int> find_next(std::vector<int>)':
prize.cpp:15:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (cx < R.size()) {
         ~~~^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80