Submission #616206

#	Time	Username	Problem	Language	Result	Execution time	Memory
616206		rrrr10000	The Big Prize (IOI17_prize)	C++14	100 / 100	277 ms	11796 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define lb(v,k) (lower_bound(all(v),k)-v.bein())
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define pb emplace_back
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
const ll inf=1001001001001001001;
int find_best(int n) {
	function<vi(vi,ll,ll,ll)> sol=[&](vi v,ll L,ll R,ll S){
		vi res;
		if(S==0)return res;
		if(v.size()==S)return v;
		ll md=v.size()/2;
		vi srt(v.size());rep(i,v.size())srt[i]=i;
		sort(all(srt),[&](ll a,ll b){if(abs(a-md)==abs(b-md))return a<b;return abs(a-md)<abs(b-md);});
		vb done(v.size(),false);
		for(ll tt:srt){
			ll i=v[tt];done[tt]=true;
			auto tmp=ask(i);
			tmp[0]-=L;tmp[1]-=R;
			for(ll x:res)tmp[x>i]--;
			if(tmp[0]+tmp[1]!=S-res.size())res.pb(i);
			else{
				vi va,vb;
				rep(j,v.size())if(!done[j]){
					if(v[j]<i)va.pb(v[j]);
					else vb.pb(v[j]);
				}
				vi ra=sol(va,L,R+res.size()+tmp[1],tmp[0]);
				vi rb=sol(vb,L+res.size()+tmp[0],R,tmp[1]);
				for(ll x:ra)res.pb(x);
				for(ll x:rb)res.pb(x);
				break;
			}
		}
		return res;
	};
	auto calc=[&](ll k){
		ll res=0;
		while(k>1){
			res+=sqrt(k)+1;
			k=sqrt(k);
		}
		return res;
	};
	vi al(n);rep(i,n)al[i]=i;
	while(al.size()>1){
		ll ma=0,tmp;
		for(int i=al.size()-1;i>=0;i--){
			ll l=calc(i);
			if(l+i<=al.size()){
				tmp=al.size()-i+1;
				break;
			}
		}
		rep(i,min((ll)(al.size()),tmp)){
			auto tmp=ask(al[i]);
			chmax(ma,(ll)(tmp[0]+tmp[1]));
		}
		vi nal=sol(al,0,0,ma);
		al=nal;
	}
	return al[0];
}

Compilation message (stderr)

prize.cpp: In lambda function:
prize.cpp:28:14: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   28 |   if(v.size()==S)return v;
      |      ~~~~~~~~^~~
prize.cpp:38:20: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'long long unsigned int' [-Wsign-compare]
   38 |    if(tmp[0]+tmp[1]!=S-res.size())res.pb(i);
prize.cpp: In function 'int find_best(int)':
prize.cpp:67:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    if(l+i<=al.size()){
      |       ~~~^~~~~~~~~~~
prize.cpp:64:11: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |   ll ma=0,tmp;
      |           ^~~

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