Leave No One Behind

cpicpcprelimsimulation

最終更新日

Table of Contents

Loading...

問題

https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim/1657 (新しいタブで開く)

問題文

ババ抜きみたいなゲームをシミュレーションしてね。
ただし、ジョーカーはないのでみんな終了するよ。

制約

サンプル

3 1 1 2 2 3 3 3 1 1 2 3 3 2 3 1 3 2 1 3 2 5 1 5 5 4 4 3 3 2 2 1 5 1 2 3 5 4 3 1 4 5 2 5 1 2 3 5 4 3 5 4 1 2 0
0 2 3 14 8 8

考察

やるだけ。カードを持ってない状態は INF で管理するとソートできて楽だと思った (実際は有効活用できなかったけど...)

戒め: erase はよくないぞ!index がよくわからなくなるし、セグフォの温床になるぞ!
消したかどうかを配列で持っておいて、まあ毎回判定しても O(N2)O(N^2) ぐらいで間に合うでしょという判断。

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/1657/judge/7999918/C++17 (新しいタブで開く)

int main() { constexpr int INF = 1e9; while (true) { int n; cin >> n; if (n == 0) break; vector a(n, vector<int>(3, INF)); rep(i, n) cin >> a[i][0] >> a[i][1]; rep(i, n) { if (a[i][0] == a[i][1]) a[i][0] = a[i][1] = INF; } vector<bool> removed(n, false); rep(i, n) if (a[i][0] == INF) removed[i] = true; int i = 0, ans = 0; while (true) { int nxt = -1; for (int j = 1; j < a.size(); j++) { if (!removed[(j + i) % n]) { nxt = (j + i) % n; break; } } if (nxt == -1) break; if (removed[i]) { i = nxt; continue; } int minim = 0; // ↓ ソートしてるんだから有効活用しなさい rep(j, 3) if (a[i][j] < a[i][minim]) minim = j; // ↓ ソートしてr(以下略 rep(j, 3) { if (a[nxt][j] == INF) { a[nxt][j] = a[i][minim]; a[i][minim] = INF; break; } } ans++; sort(a[nxt].begin(), a[nxt].end()); if (a[nxt][0] == a[nxt][1]) { a[nxt][0] = a[nxt][1] = INF; } else if (a[nxt][2] == a[nxt][1]) { a[nxt][2] = a[nxt][1] = INF; } sort(a[nxt].begin(), a[nxt].end()); if (a[nxt][0] == INF) removed[nxt] = true; sort(a[i].begin(), a[i].end()); if (a[i][0] == INF) removed[i] = true; i = nxt; } cout << ans << endl; } return 0; }