[AGC005C]Tree Restoring

Tree Restoring

AGC005C

#define dis 要求离它距离最远的点与它的距离
很显然这里距离最远的两个点构成了树的直径。
加入这两个点dis不相等，那就完了。

既然已经构造出树的直径，那dis的最小值也确定了。
分奇偶讨论一下树的直径与dis最小值的关系。
假如$dis_ {min}!=(dis_ {max}+1)/2$，那也完了。
如果除了树的中心还有点$dis=dis_ {min}$，那也完了。
这是一条链，到端点的距离是线性的，所以两边都各需要dis在$(dis_ {min} dis_ {max})$上每个位置的一个数。
剩下的dis在$(dis_ {min} dis_ {max}]$之间的数，可以挂在直径上，不会影响结果。

code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
const int N=102;
int n,a[N];

inline int nxi(){
	int x=0;
	char c;
	while((c=getchar())>'9'||c<'0');
	while(x=x*10-48+c,(c=getchar())>='0'&&c<='9');
	return x;
}

inline bool jdg(){
	int dis=a[n],tp=dis&1;
	if(a[1]!=(dis+1)>>1) return 0;
	if(a[n-1]!=dis||(a[1]==a[2])^tp){
		return 0;
	}
	tp+=1;
	if(a[tp+1]==a[1]) return 0;
	int ts=2;
	for(int i=tp+1;i<=n;++i){
		if(a[i]!=a[i-1]){
			if(ts<2||a[i]-a[i-1]>1) return 0;
			ts=0;
		}
		++ts;
	}
	return 1;

}

int main(){
#ifndef ONLINE_JUDGE
//	freopen("c.in","r",stdin);
#endif
	n=nxi();
	for(int i=1;i<=n;++i){
		a[i]=nxi();
	}
	std::sort(a+1,a+n+1);
	puts(jdg()?"Possible":"Impossible");
	return 0;
}