Submission #789307

#	Time	Username	Problem	Language	Result	Execution time	Memory
789307		khshg	The Big Prize (IOI17_prize)	C++14	0 / 100	13 ms	11224 KiB

prize

#include "prize.h"
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;
#define pb push_back
 
int val, B, y;
vector<int> non_lolipop, x, L;
 
vector<vector<int>> memo;
vector<int> K(int i) {
//	if(i >= (int)memo.size()) exit(0);
	if(memo[i][0] != -1) return memo[i];
	return memo[i] = ask(i);
}
 
void find(int l, int r){
	if (l > r || K(l)[1] == y)return;
	if(K(l)[0] + K(l)[1] != val) {
		non_lolipop.pb(l);
		find(l + 1, r);
		return;
	}
	int bl = l, br = r;
	while (bl != br){
		int bm = (bl + br) / 2;
		if (K(bm) == K(l)) {
			bl = bm + 1;
		} else {
			br = bm;
		}
	}
	find(bl, r);
}
 
int find_best(int n){
	memo.resize(n, {-1, -1});
	B = max(1, n / 472);
	for (int i = 0; i < n; i += B){
		x = K(i);
		val = max(val, x[0] + x[1]);
	}
	for (int i = 0; i < n; i += B){
		for (int j = i; j < i + B && j < n; j++){
			x = K(j);
			if (x[0] + x[1] != val){
				non_lolipop.pb(j);
				continue;
			}
			L.pb(j);
			break;
		}
	}
	for (int i = 0; i < (int)L.size(); i++){
		if (i + 1 == (int)L.size()){
			x = K(L[i]);
			y = max(0, n - (L[i] / B + 1) * B);
		}else{
			y = B * (L[i + 1] / B - L[i] / B - 1) + L[i + 1] % B;
			x = K(L[i]);
			vector<int> z = K(L[i + 1]);
			y += z[1];
		}
		find(L[i], min(n - 1, L[i] / B * B + B - 1));
	}
	for (int i = 0; i < non_lolipop.size(); i++){
		x = K(non_lolipop[i]);
		if (x[0] + x[1] == 0)return non_lolipop[i];
	}
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for (int i = 0; i < non_lolipop.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~

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