UTPC2013 D 壊れかけのヒープ

問題

日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_04）

二分ヒープを表す長さnの配列a[i]がある。
二分ヒープを表す長さm（m≧n)の配列b[i]で、b[i]の後ろn個がa[i]になっているものが存在すれば、その最小のmを、なければ-1を答えよ。

制約条件

n≦100
a[i]≦10^9
ここで、配列a[i]が二分ヒープをあらわすとは、
a[i]の要素が全て異なる0以上の整数であり、a[i]はa[i*2 + 1], a[i*2 + 2]（存在すれば）より真に小さいことを言うものとする。

方針

a[i]が全部葉になるようなmまで考えるだけで十分らしい。（きちんと証明してない）
なので、m≦1000くらいまでを全部試してみればいい。

ある数より小さい数を求める上手い実装が思い浮かばなかったので、
大きい数だけ座標圧縮して、union-findもどき的なものを作って適当に小さい数を答えるようにした。

ソースコード

const int MX = 20000;
int n, a[100], b[10000], next[20000];
 
int get(int x){
	if(x < 0) return -1;
	if(next[x] == x) return x;
	return next[x] = get(next[x]);
}
 
bool ok(int m){
	rep(i, MX) next[i] = i;
	set<int> use;
	
	rep(i, n){
		b[m - 1 - i] = a[n - 1 - i];
		if(use.count(a[i])) return 0;
		use.insert(a[i]);
		if(a[i] < MX) next[a[i]] = get(a[i] - 1);
	}
	
	//rep(i, m) cerr<<b[i]<<" ";cerr<<endl;
	
	for(int i = m - 1; i >= m - n; i--){
		int x = i * 2 + 1, y = i * 2 + 2;
		
		if(x < m && y < m){
			if(b[x] == b[y]) return 0;
			if(b[x] > b[y]) swap(x, y);
		}
		int z = x < m ? b[x] : inf + 100000;
		if(b[i] >= z) return 0;
	}
	
	for(int i = m - n - 1; i >= 0; i--){
		int x = i * 2 + 1, y = i * 2 + 2;
		
		if(x < m && y < m){
			if(b[x] == b[y]) return 0;
			if(b[x] > b[y]) swap(x, y);
		}
		int z = x < m ? b[x] - 1 : MX - 1;
		z = get(z);
		if(z < 0) return 0;
		
		next[z] = get(next[z] - 1);
		b[i] = z;
	}
	return 1;
}
 
int main(){
	cin >> n;
	vi big;
	rep(i, n){
		cin >> a[i];
		if(a[i] >= MX) big.pb(a[i]);
	}
	sort(all(big));
	big.erase(unique(all(big)), big.end());
	
	rep(i, n) if(a[i] >= MX){
		int pos = lower_bound(all(big), a[i]) - big.begin();
		a[i] = MX - big.size() - 1 + pos;
	}
	
	int j = n;
	for(j = n; j < 2000 && !ok(j); j++);
	cout << (ok(j) ? j : -1) << endl;
	
	//rep(i, j) cerr<<b[i]<<" ";cerr<<endl;
	
	return 0;
}