Codeforces 156 B. Suspects

問題

n人の容疑者がいて、それぞれは
"x番の人が犯人である"または、
"x番の人は犯人でない"と主張している。

容疑者のうち、m人は本当のことを言っていることがわかっている。
このとき、それぞれの容疑者について、
確実に本当のことを言っている人にはTruthを、
確実に嘘をついている人にはLieを、
どちらもありえる人にはNot definedを出力せよ。

制約条件

n≦10^5

方針

それぞれの人について、
その人が本当のことを言っている、嘘をついていると仮定してみて、
人数が矛盾するならその人は嘘つき、あるいは本当のことを言っている。
どちらでも矛盾がないならNot defined.

人数を調べるには、
「x番目の人が犯人だとすると何人本当のことを言っているか」を
あらかじめ計算しておけばいい。

ソースコード

int n, m, a[100001];
int cnt[100001], base;

int main(){
	cin>>n>>m;
	rep(i,n){
		cin>>a[i];
		if(a[i]<0)cnt[-a[i]]++;
		else cnt[a[i]]--, base++;
	}
	int z=0;
	rep(i,n)if(base+cnt[i+1]==n-m)z++;
	
	rep(i,n){
		bool lie=1,truth=1;
		if(base+cnt[abs(a[i])]==n-m)z--;
		if(a[i]<0)cnt[-a[i]]--;
		else cnt[a[i]]++, base--;
		if(base+cnt[abs(a[i])]==n-m-(a[i]<0)){
			if(z==0&&a[i]>0)lie=0;
			if(z==0&&a[i]<0)truth=0;
		}
		else{
			if(a[i]>0)truth=0;
			else lie=0;
		}
		
		if(lie&&truth)cout<<"Not defined"<<endl;
		else cout<<(lie?"Lie":"Truth")<<endl;
		
		if(a[i]<0)cnt[-a[i]]++;
		else cnt[a[i]]--, base++;
		if(base+cnt[abs(a[i])]==n-m)z++;
	}
	return 0;
}