Submission #1252339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252339		PlayVoltz	커다란 상품 (IOI17_prize)	C++20	0 / 100	3 ms	2056 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int mx=0;
vector<pii> ooga;

pii query(int a){
	if (ooga[a].fi!=-1)return ooga[a];
	vector<int> res=ask(a);
	if (!(res[0]+res[1]))throw a;
	return ooga[a]=mp(res[0], res[1]);
}

void dnc(int l, int r, int cl, int cr){
	if (l>r)return;
	for (int i=0; i<=r-l; ++i){
		int lm=(l+r)/2-i/2, rm=(l+r)/2+(i+1)/2, m=(i%2?rm:lm);
		pii res=query(m);
		if (res.fi+res.se==mx){
			if (i%2){
				if (res.se>cr)dnc(rm+1, r, res.fi, cr);
				if (res.fi-rm+lm>cl)dnc(l, lm-1, cl, res.se+rm-lm);
			}
			else{
				if (res.fi>cl)dnc(l, lm-1, cl, res.se);
				if (res.se-rm+lm>cr)dnc(rm+1, r, res.fi+rm-lm, cr);
			}
		}
	}
}

int find_best(int n){
	if (n==1)return 0;
	ooga.resize(n, mp(-1, -1));
	int id=0;
	for (int i=0; i<sqrt(n)+30&&mx<27; ++i){
		pii res=query(i);
		if (res.fi+res.se>mx)mx=res.fi+res.se, id=i;
	}
	try{
		dnc(id, n-1, id, 0);
	}
	catch(int a){
		return a;
	}
}

Compilation message (stderr)

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

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