問題
https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim/1657 (新しいタブで開く)
問題文
ババ抜きみたいなゲームをシミュレーションしてね。
ただし、ジョーカーはないのでみんな終了するよ。
制約
- 人数
- カードの番号
- 同じカードの番号は 2 枚ずつ
- 入力行数は 10000 以下 (≒ N の総和)
サンプル
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 がよくわからなくなるし、セグフォの温床になるぞ！
消したかどうかを配列で持っておいて、まあ毎回判定しても ぐらいで間に合うでしょという判断。
コード
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;
}