Submission #425271

#	Time	Username	Problem	Language	Result	Execution time	Memory
425271		NachoLibre	The Big Prize (IOI17_prize)	C++17	0 / 100	14 ms	11160 KiB

prize

#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef long long ll;
#ifndef wambule
#include "prize.h"
#else
vint ask(int) { return vint(0); }
#endif

mt19937_64 rnd(time(0));
int R(int l, int r) {
	return l + rnd() % (r - l + 1);
}

vvint cch;
vint A(int i) {
	if(cch[i][0] == -1) cch[i] = ask(i);
	return cch[i];
}

int find_best(int n) {
	cch.resize(n, vint(2, -1));
	int cm = 0;
	for(int i = 1; i <= 30; ++i) {
		int x = R(0, n - 1);
		cm = max(cm, A(x)[0] + A(x)[1]);
		if(A(x)[0] + A(x)[1] == 0) return x;
	}
	for(int i = 0; i < n; ++i) {
		if(A(i)[0] + A(i)[1] == +0) return i;
		if(A(i)[0] + A(i)[1] == cm) {
			int l = i, r = n - 1, m;
			while(l < r) {
				int m = l + r + 1 >> 1;
				while(A(m)[0] + A(m)[1] < cm) {
					--m;
					r = m;
				}
				if(A(m)[1] == A(i)[1]) l = m;
				else r = m - 1;
			}
			i = l + 1;
		}
	}
	return 0;
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}
#endif

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:37:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~
prize.cpp:35:26: warning: unused variable 'm' [-Wunused-variable]
   35 |    int l = i, r = n - 1, m;
      |                          ^

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