Submission #40588

#	Time	Username	Problem	Language	Result	Execution time	Memory
40588		PowerOfNinjaGo	The Big Prize (IOI17_prize)	C++14	95.89 / 100	32 ms	12916 KiB

prize

#ifndef Chai
#include "prize.h"
#endif
#ifdef Chai
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector< ii > vii;
typedef long long LL;
int lim = 472;
vi res[200005];
int best;
int solve(int a, int b, int five, int fivestoleft, int fivestoright)
{
	if(five == 0)
	{
		for(int i = b; i>= a; i--)
		{
			res[i] = ask(i);
			if(res[i][0]+res[i][1] == 0) return i;
		}
		return -1;
	}
	if(five == b-a+1) return -1;
	if(a> b) return -1;
	int M = (a+b)/2;
	int locate = -1;
	res[M] = ask(M);
	if(res[M][0]+res[M][1] == 0) return M;
	if(res[M][0]+res[M][1] == best) locate = M;
	int zone_left, zone_right;
	zone_left = zone_right = M;
	for(int i = 1; locate==-1; i++)
	{
		res[M-i] = ask(M-i);
		if(res[M-i][0]+res[M-i][1] == 0) return M-i;
		if(res[M-i][0]+res[M-i][1] == best) 
		{
			locate = M-i;
			break;
		}
		zone_left = M-i;
		res[M+i] = ask(M+i);
		if(res[M+i][0]+res[M+i][1] == 0) return M+i;
		if(res[M+i][0]+res[M+i][1] == best)
		{
			locate = M+i;
			break;
		}
		zone_right = M+i;
	}
	assert(locate != -1);
	int ans1;
	int Left = res[locate][0], Right = res[locate][1];
	if(locate> M)
	{
		int szL = zone_left-a;
		int szR = b-locate;
		int fL = szL-(Left-fivestoleft);
		int fR = szR-(Right-fivestoright);
		int nfL = szL-fL;
		int nfR = szR-fR;
		ans1 = solve(a, zone_left-1, fL, fivestoleft, nfR+fivestoright);
		if(ans1 != -1) return ans1;
		return solve(locate+1, b, fR, fivestoleft+nfL, fivestoright);
	}
	else
	{
		int szL = locate-a;
		int szR = b-zone_right;
		int fL = szL-(Left-fivestoleft);
		int fR = szR-(Right-fivestoright);
		int nfL = szL-fL;
		int nfR = szR-fR;
		ans1 = solve(a, locate-1, fL, fivestoleft, nfR+fivestoright);
		if(ans1 != -1) return ans1;
		return solve(zone_right+1, b, fR, fivestoleft+nfL, fivestoright);
	}
}
int find_best(int n) 
{
	best = 0;
	int five = 0;
	for(int i = 0; i< n; i++) res[i].assign(2, -1);
	for(int i = 0; i< lim; i++)
	{
		vi x = ask(i);
		res[i] = x;
		if(x[0]+x[1] == 0) return i;
		best = max(best, x[0]+x[1]);
	}
	int left_border = -1, right_border = -1;
	for(int i = 0; i< lim; i++)
	{
		if(res[i][0]+res[i][1] == best)
		{
			left_border = i;
			five++;
		}
	}
	int tot5 = n-best;
	int k = solve(left_border+1, n-1, tot5-five, left_border+1-five, 0);
	return k;
}
/*
8
3 2 3 1 3 3 2 3
*/

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:99:24: warning: unused variable 'right_border' [-Wunused-variable]
  int left_border = -1, right_border = -1;
                        ^

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