Codeforces 420 Coder-Strike 2014 - Finals (online edition, Div. 1) B. Online Meeting

問題

n人の人がいて、その人たちが参加したチャットの入退室のログがある。
ログはある時刻からある時刻までしか記録されていないが、その間の記録は全て含まれる。
このチャットにおいて、誰か一人でもオンラインになっているときは、
必ずその人がオンラインになっているという人をリーダーとする。


リーダーの候補としてありえる人を全て出力せよ。

制約条件

n≦10^5
ログの個数≦10^5
ログは時系列順で、二つのログが同時におこったことはない

方針

一度もログに現れていない人は、リーダーの候補。
ログに現れた人がリーダーになりうるかどうかを考えるときは、
ログに現れてない人は全員オフラインだったと考えてよい。


退室が最初に来てる人は最初からオンラインだった。
ここから状態をシミュレートしていく。


最後の一人じゃいのに退室した人は候補から外す。
最初の一人じゃないのに入室した人は候補から外す。
最後の一人で退室した人がいたら、
次に入室した人がその人でなければ候補がいなくなる。

これでよい。

ソースコード

int n, m, x[100010];
char c[100010];

int main(){
	scanf("%d%d", &n, &m);
	set<int> used, on, ans, cand;
	
	rep(i, m){
		scanf(" %c%d", c + i, x + i);
		if(c[i] == '-'){
			if(!used.count(x[i])) on.insert(x[i]);
		}
		used.insert(x[i]);
	}
	
	for(int i = 1; i <= n; i++){
		if(!used.count(i)) ans.insert(i);
		else cand.insert(i);
	}
	
	int last = -1;
	bool ok = 1;
	
	rep(i, m + 1){
		if(c[i] == '+'){
			if(on.size()) cand.erase(x[i]);
			else{
				if(last >= 0 && last != x[i]) ok = 0;
			}
			on.insert(x[i]);
		}
		else{
			on.erase(x[i]);
			if(on.size()) cand.erase(x[i]);
			else last = x[i];
		}
	}
	
	if(ok) each(i, cand) ans.insert(*i);
	printf("%d\n", ans.size());
	each(i, ans) printf("%d ", *i);
	
	return 0;
}