Submission #834110

#	Time	Username	Problem	Language	Result	Execution time	Memory
834110		caganyanmaz	The Big Prize (IOI17_prize)	C++17	20 / 100	94 ms	432 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 = ask(j);
			if (v[0] + v[1] < ecount)
			{
				l = j;
				expensive[j] = true;
				break;
			}
			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:44:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |  while (vv.size() < ecount)
      |         ~~~~~~~~~~^~~~~~~~
prize.cpp:49:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |    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: 0 / 80