Submission #297190

#	Time	Username	Problem	Language	Result	Execution time	Memory
297190		Muhammetali	The Big Prize (IOI17_prize)	C++11	0 / 100	15 ms	9984 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
pi para={-1,-1};
vi v[200001];
vector<int> sor(int k)
{
	if (v[k].size()>0 && v[k][0]+v[k][1]==0)v[k]=ask(k);
	return v[k];
}
void solve(int l,int r,int a,int b)
{
	if (l>r || a+b==para.f)return;
	int mid=(l+r)/2;
	int x=0;
	for (int i=mid;i>=l;i--)
	{
		vi res=sor(i);
		if (res[0]+res[1]>=para.f)
		{
			if (i>l) solve(l,i-1,a,res[1]);
			if (i<r) solve(i+1,r,res[0]+x,b);
			return;
		}
		x++;
	}
	if (r>mid)solve(mid+1,r,a+x,b);
}
int find_best(int n)
{
	for(int i=0;i<min(500,n);i++)
	{
		vi res=sor(i);
		if(res[0]+res[1]>para.f) para={res[0]+res[1],i};
		if (para.f>100) break;
	}
	solve(0,n-1,0,0);
	for (int i=0;i<n;i++) if (sz(v[i])>0 && v[i][0]+v[i][1]==0)return i;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^

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