AGC005 C - Tree Restoring

問題

頂点数がnで全てのi=1,2,...,nについて頂点iと最も遠い頂点の距離がa[i]となるような木が作れるか判定

解法

↓木が作れる場合の作り方
まずk = max(a,a+n)とし、直径kの一直線な木を作る(写真の青色部分)
それで余った頂点iは、最も遠い頂点との距離がa[i]-1であるような頂点に直接繋げば消化できる(赤色部分)

逆にこの途中で点が足りなかったりa[i]が実現できない点があったりしたら木は作れない

実装

上の写真からわかるようにa[i]が(k+1)/2未満だとどうやっても実現できないからImpossible
最初の一直線な木を作る時点で足りない点があってもダメ
余った頂点を木にくっつけていくときも、(k+1)/2未満の点にくっつける必要がある頂点があったらダメ

int n, k, a[101], b[101];
 
void fin() {
	cout << "Impossible" << endl;
	exit(0);
}
 
signed main() {
	cin >> n;
	rep(i,n) {
		cin >> a[i];
		b[a[i]]++;
	}
	k = *max_element(a,a+n);
	rep(i,n) if (a[i]<(k+1)/2) fin();
	if (k%2) reps(i,(k+1)/2,k+1) b[i] -= 2;
	else reps(i,k/2,k+1) b[i] -= 2-(i==k/2);
	rep(i,k+1) if (b[i]) {
		if (b[i]<0) fin();
		else if (i-1<(k+1)/2) fin();
	}
	cout << "Possible" << endl;
}