Submission #789274

#	Time	Username	Problem	Language	Result	Execution time	Memory
789274		enerelt14	The Big Prize (IOI17_prize)	C++14	0 / 100	13 ms	11276 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 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