Submission #137808

#	Time	Username	Problem	Language	Result	Execution time	Memory
137808		MAMBA	The Big Prize (IOI17_prize)	C++17	20 / 100	70 ms	956 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define all(x) x.begin(),x.end()

typedef vector<int> vi;

map<int , vi> mp;
inline vi F(int i) {
	if (mp.count(i)) return mp[i];
	if (mp.size() + 1 > 10000) assert(0);
	return (mp[i] = ask(i));
}

inline int sum(vi me) {
	return accumulate(all(me) , 0);
}

int least, ans;
bitset<400000> mark;

void solve(int l , int r, int le , int ri) {

	if (ans != -1) return;
	if (l >= r) return;
	if (le + ri == least) return;
	int mid = l + r >> 1;
	bool happy = false;
	rep(i , 0 , r - l) {
		if (i & 1) mid -= i;
		else mid += i;
		vi me = F(mid);
		mark[mid] = true;
		if (sum(me) == 0) {
			ans = mid;
			return;
		}
		if (sum(me) == least) {
			happy = true;
			break;
		}
		if (le + ri + i + 1 == least) return;
	}

	if (!happy) return;

	int ptr = l;
	while (!mark[ptr]) ptr++;
	int ptr2 = ptr;
	while (sum(F(ptr2)) != least) ptr2++;

	int ptr3 = r - 1;
	while (!mark[ptr3]) ptr3--;
	int ptr4 = ptr3;
	while (sum(F(ptr4)) != least) ptr4--;


	solve(l , ptr , le , ptr2 - ptr + F(ptr2)[1]);


	solve(ptr3 + 1 , r , ptr3 - ptr4 + F(ptr4)[0], ri);

}

int find_best(int n) {

	mp.clear();
	rep(i , 0 , n) mark[i] = false;


	least = -1; ans = -1;
	for (int i = 1; (i - 2) * (i - 2) <= n; i++) {
		least = max(least , sum(F(i - 1)));
		if (sum(F(i - 1)) == 0) return i - 1;
	}


	solve(0 , n , 0 , 0);

	return ans;
}

Compilation message (stderr)

prize.cpp: In function 'void solve(int, int, int, int)':
prize.cpp:30:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~

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