Submission #113531

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

prize

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

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

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

vector<int> find_next(vector<int> R) {
	int S = sqrt(R.size()) + 1;
	int TT = 0, U = 1; while (U <= 10000) { U *= S; TT++; }
	
	int maxn = 0;
	for (int i = 0; i < TT; i++) {
		vector<int> P = asks(R[rand() % R.size()]);
		maxn = max(maxn, 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] != maxn) { T.push_back(R[cx]); cx++; continue; }
		if (cx + 1 == (int)R.size()) break;
		
		int B = 512;
		if (R.size() <= 500) B = 32768;
		int cl = 0, cr = min((int)R.size() - cx, B), cm, maxn = -1; bool flag = false;
		while (true) {
			bool terminate = false; if (cr - cl <= 1) terminate = true;
			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 (terminate == true) break;
		}
		if (maxn == (int)R.size() - 1) break;
		T.push_back(R[maxn + 1]);
		cx = maxn + 2;
	}
	//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];
}

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