AOJ 0617: Ball

良問

解法

nが3^*のときは解を二分探索すると解けるから、ダミーの貴族を追加する。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 401000
int d1[N], p[N], d2[N], d[N], s[N];
int n, m, n2;
int rest, off, lm;

int rec(int l, int r){
	if(r-l==1){
		if(s[l]==-1) return 1;
		if(s[l]==1) return 0;
		return N;
	}
	int a[3], w = (r-l)/3;
	for(int i = 0; i < 3; i++)
		a[i] = rec(l+w*i, l+w*(i+1));
	sort(a, a+3);
	return min(N, a[0]+a[1]);
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; i++) scanf("%d%d", d1+i, p+i);
	for(int i = 0; i < n-m; i++) scanf("%d", d2+i);
	memcpy(d, d1, m*sizeof(int));
	memcpy(d+m, d2, (n-m)*sizeof(int));
	sort(d, d+n);
	int th = 3, cth = 1;
	while(th < n){
		th *= 3;
		cth++;
	}
	rest = (th-n)/2; off = rest*3; lm = n-rest;
	for(int i = 0; i < m; i++){
		if(p[i]>lm) p[i] = (p[i]-lm-1)*3;
		else p[i] = p[i]-1+off;
	}
	int lb = 0, ub = n;
	while(ub-lb>1){
		int md = (lb+ub)/2;
		int t = d[md];
		memset(s, -1, sizeof(s));
		for(int i = 0; i < rest; i++){
			s[3*i+1] = 0;
			s[3*i+2] = 1;
		}
		for(int i = 0; i < m; i++)
			s[p[i]] = d1[i]>=t;
		int sm = 0;
		for(int i = 0; i < n-m; i++)
			sm += d2[i]>=t;
		int nm = rec(0, th);
		if(nm<=sm) lb = md;
		else ub = md;
	}
	printf("%d\n", d[lb]);

	return 0;
}