Submission #216677

#	Time	Username	Problem	Language	Result	Execution time	Memory
216677		davitmarg	The Big Prize (IOI17_prize)	C++17	20 / 100	28 ms	5624 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;
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 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));
	srand(mx);
	for (int i = 0; i < n; i++)
	{
		if (rand() % 10 < 2)
			continue;
		int now = get(i);
		if (now == mx)
		{
			int l = i, r = n - 1, m, pos;
			while (l <= r)
			{
				m = (l + r) / 2;
				if (Ask(m)==Ask(i))
				{
					pos = m;
					l = m + 1;
				}
				else
					r = m - 1;
			}
			i = pos;
		}
		else if (now == 0)
		{
			ans = i;
			break;
		}
	}
	return ans;
}

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



/*




*/

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:52:2: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  for (int i = 0; i < n; i++)
  ^~~

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