Submission #113541

#	Time	Username	Problem	Language	Result	Execution time	Memory
113541		E869120	The Big Prize (IOI17_prize)	C++14	20 / 100	95 ms	3092 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

int A[200009], QQ; map<int, vector<int> >Map;

vector<int> asks(int pos) {
	if (Map[pos].size() >= 1) return Map[pos];
	Map[pos] = ask(pos); QQ++;
	return Map[pos];
}

vector<int> find_next(vector<int> R) {
	int S = sqrt(R.size()) + 1;
	int TT = 0, U = 1; while (U <= 1000) { U *= S; TT++; }
	
	int maxp = 0;
	for (int i = 0; i < TT; i++) {
		vector<int> P = asks(R[rand() % R.size()]);
		maxp = max(maxp, P[0] + P[1]);
	}
	
	int cx = 0; vector<int> T;
	while (cx < (int)R.size()) {
		vector<int> P = asks(R[cx]);
		if (P[0] + P[1] != maxp) { T.push_back(R[cx]); cx++; continue; }
		if (cx + 1 == (int)R.size()) break;
		
		int B = 512;
		if (R.size() <= 500) B = 32;
		if (R.size() <= 30) B = 8;
		int cl = 0, cr = min((int)R.size() - cx, B), cm, maxn = cx; bool flag = false;
		while (cr - cl >= 2) {
			cm = (cl + cr) / 2;
			//cout << "cx = " << cx << ", cl = " << cl << ", cr = " << cr << ", cm = " << cm << ", maxn = " << maxn << endl;
			vector<int> Q = asks(R[cx + cm]);
			if (P == Q) {
				if (flag == true) cl = cm;
				else cr *= 2;
				if (flag == false && cr >= (int)R.size() - cx) { flag = true; cr = R.size() - cx; }
				maxn = max(maxn, cx + cm);
			}
			else { cr = cm; flag = true; }
		}
		if (maxn == (int)R.size() - 1) break;
		T.push_back(R[maxn + 1]);
		cx = maxn + 2;
		if (T.size() == maxp) break;
	}
	//for (int i = 0; i < T.size(); i++) cout << T[i] << ", "; cout << endl;
	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:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (T.size() == maxp) break;
       ~~~~~~~~~^~~~~~~

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