Submission #803236

#	Time	Username	Problem	Language	Result	Execution time	Memory
803236		Username4132	The Big Prize (IOI17_prize)	C++14	100 / 100	48 ms	3528 KiB

prize

#include "prize.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

const int MAXN = 200010;
int n, can=-1, offset[MAXN], sum;
pii info[MAXN];
vector<int> values, obt;

pii myask(int i){
	if(info[i].F==-1){
		vector<int> ret = ask(i);
		info[i] = {ret[0], ret[1]};
	}
	return info[i];
}

bool dfs(int l, int r, int x, int y){
	if(l==r || x+y==sum) return true;
	int mid = (l+r)>>1, mn=n+2, mx=-1, lx, ly, cnt=0, lst=mid;
	forn(i, r-l){
		int pt = mid + offset[i];
		lst=pt;
		mn = min(mn, pt);
		mx = max(mx, pt);
		pii res = myask(values[pt]);
		lx=res.F, ly=res.S;
		if(res.F + res.S > sum){
			sum = res.F + res.S;
			can = values[pt];
			return false;
		}
		if(res.F + res.S < sum) obt.PB(values[pt]);
		if(res.F + res.S == sum) break;
		++cnt;
	}

	int x2=lx, y2=ly;
	if(lst>mid) y2+=cnt;
	else x2+=cnt;

	if(!dfs(l, mn, x, y2)) return false;
	if(!dfs(mx+1, r, x2, y)) return false;
	return true;
}


int find_best(int N) {
	n=N;
	values.resize(n);
	forn(i, n) info[i]={-1, -1}, values[i]=i;
	forn(i, n) offset[i]=(i&1? -((i+1)>>1) : ((i+1)>>1));
	while(values.size()>1){
		sum = -1;
		while(!dfs(0, values.size(), 0, 0)){
			obt.clear();
			if(sum==0) return can;
		}
		swap(values, obt);
		obt.clear();
		sort(values.begin(), values.end());
	}
	return values.front();
}

Compilation message (stderr)

prize.cpp: In function 'bool dfs(int, int, int, int)':
prize.cpp:26:14: warning: 'x2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |  if(l==r || x+y==sum) return true;
      |             ~^~
prize.cpp:49:9: warning: 'ly' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |  if(!dfs(l, mn, x, y2)) return false;
      |      ~~~^~~~~~~~~~~~~~

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