Submission #216697

#	Time	Username	Problem	Language	Result	Execution time	Memory
216697		davitmarg	The Big Prize (IOI17_prize)	C++17	90 / 100	74 ms	6264 KiB

prize

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#include "prize.h"
using namespace std;

const int N = 200005;

int used[N], n, k = 500, pre[N],len;
vector<int> res[N];

vector<int> Ask(int pos)
{
	if (used[pos])
		return res[pos];
	used[pos] = 1;
	return res[pos] = ask(pos);
}
int get(int pos)
{
	return Ask(pos)[0] + Ask(pos)[1];
}

int letsfind(int x)
{
	int id = x / len;
	if (Ask(id * len) != Ask(x))
	{
		int l = x, r = min(x + len - 1, n - 1), m, pos;
		while (l <= r)
		{
			m = (l + r) / 2;
			if (Ask(m) == Ask(x))
			{
				pos = m;
				l = m + 1;
			}
			else
				r = m - 1;
		}
		return pos;
	}
	else
	{
		int pos = -1;
		for (int i = id; i <= k && i * len < n; i++)
			if (Ask(i * len) == Ask(x))
				pos = pre[i];
		return pos;
	}
}

int find_best(int nn)
{
	n = nn;
	int mx = 0, ans = -1;
	for (int i = 0; i < min(500, n); i++)
		mx = max(mx, get(i));

	k = ((int)sqrt(n)) / 2 + 1;
	len = n / k;

	for (int i = 0; i <= k; i++)
	{
		int l = i * len, r = min(n-1, l + len - 1), m;
		pre[i] = -1;
		while (l <= r && get(i * len) == mx)
		{
			m = (l + r) / 2;
			if (Ask(m) == Ask(i * len))
			{
				pre[i] = m;
				l = m + 1;
			}
			else
				r = m - 1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		int now = get(i);
		if (now == mx)
			i = letsfind(i);
		else if (now == 0)
		{
			ans = i;
			break;
		}
	}
	return ans;
}

//int main()
//{
//	
//	return 0;
//}



/*

8
3 2 3 1 3 3 2 3

10
2 2 2 2 2 1 2 2 2 2


*/

Compilation message (stderr)

prize.cpp: In function 'int letsfind(int)':
prize.cpp:49:46: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int l = x, r = min(x + len - 1, n - 1), m, pos;
                                              ^~~

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