Submission #715956

#	Time	Username	Problem	Language	Result	Execution time	Memory
715956		myrcella	The Big Prize (IOI17_prize)	C++17	0 / 100	5 ms	296 KiB

prize

//by szh
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
#include "prize.h"
 
const int maxn = 2e5+10;
 
int ans;
set <int> pos;
vector <int> val;
int sum;
set <int> hi;
 
void solve(int l,int r,int pre,int suf) {
	if (l>r) return;
	int midl = l+r>>1;
	int midr = midl;
	vector <int> tmp = {-1,-1};
	int mid;
	while (midl>=l) {
		tmp = ask(midl);
		if (tmp[0]+tmp[1]==sum) break;
		if (tmp[0]+tmp[1]==0) {
			ans = midl;
			return;
		}
		pos.insert(midl);
		midl--;
	}
	if (midl<l) {
		midr++;
		while (midr<=r) {
			tmp = ask(midr);
			if (tmp[0]+tmp[1]==sum) break;
			if (tmp[0]+tmp[1]==0) {
				ans = midr;
				return;
			}
			pos.insert(midr);
			midr++;
		}
      	if (midr>r) return;
      	if (tmp[1]-suf>0) solve(midr+1,r,tmp[0],suf);
	}
	else {
      if (tmp[0]-pre>0) solve(l,midl-1,pre,tmp[1]);
      if (tmp[1]-(midr-midl)-suf>0) solve(midr+1,r,tmp[0]+midr-mid,suf);
    }
	return;
}
 
int find_best(int n) {
	int ed;
	rep(i,0,472) {
		vector <int> tmp = ask(i);
		if (tmp[0]+tmp[1]==0) return i;
		val.pb(tmp[0]+tmp[1]);
		hi.insert(val.back());
		ed = i;
		if (SZ(hi)==4) break;
	}
	
	sort(ALL(val));val.erase(unique(ALL(val)),val.end());
	sum=val.back();
	solve(ed+1,n-1,0,0);
	return ans;
}

Compilation message (stderr)

prize.cpp: In function 'void solve(int, int, int, int)':
prize.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |  int midl = l+r>>1;
      |             ~^~
prize.cpp:66:42: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |       if (tmp[1]-(midr-midl)-suf>0) solve(midr+1,r,tmp[0]+midr-mid,suf);
      |                                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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