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; }