Submission #834119

#	Time	Username	Problem	Language	Result	Execution time	Memory
834119		caganyanmaz	The Big Prize (IOI17_prize)	C++17	90 / 100	78 ms	428 KiB

prize

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

//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int BLOCK_SIZE = 500;
constexpr static int LBN = 5000; 
constexpr static int MXN = 2e5;
bitset<MXN> expensive;

int brute(int n);
int find_best(int n)
{
	// Get rid of smaller cases
	if (n < 5000)
		return brute(n);
	// Finding one cheap prize (getting expesive ones are better)
	int ecount = 0;
	vector<int> c;
	for (int i = 0; i < BLOCK_SIZE; i++)
	{
		vector<int> v = ask(i);
		c.pb(v[0] + v[1]);
		ecount = max(ecount, c.back());
	}
	int s = 0;
	vector<int> vv;
	for (int i = 0; i < BLOCK_SIZE; i++)
	{
		if (c[i] != ecount)
		{
			expensive[i] = true;
			vv.pb(i);
		}
	}
	while (vv.size() < ecount)
	{
		int l = 0, r = n;
		while (r - l > 1)
		{
			int m = l+r>>1;
			int j = m;
			while (expensive[j])
				j++;
			vector<int> v;
			if (j != n)
			{
				v = ask(j);
				if (v[0] + v[1] < ecount)
				{
					l = j;
					expensive[j] = true;
					break;
				}
			}
			else
			{
				v.pb(ecount);
			}
			if (v[0] > upper_bound(vv.begin(), vv.end(), j) - vv.begin())
				r = m;
			else
				l = m;
		}
		vv.insert(lower_bound(vv.begin(), vv.end(), l), l);
	}
	for (int i = 0; i < n; i++)
	{
		if (expensive[i])
		{
			vector<int> v = ask(i);
			if (v[0] + v[1] == 0)
				return i;
		}
	}

	return -1;
}
int brute(int n)
{
	for (int i = 0; i < n; i++)
	{
		vector<int> v = ask(i);
		if (v[0] + v[1] == 0)
			return i;
	}
	return -1;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:43:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |  while (vv.size() < ecount)
      |         ~~~~~~~~~~^~~~~~~~
prize.cpp:48:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |    int m = l+r>>1;
      |            ~^~
prize.cpp:33:6: warning: unused variable 's' [-Wunused-variable]
   33 |  int s = 0;
      |      ^

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