結果

問題 No.3086 Re One Two
ユーザー Today03
提出日時 2025-04-04 21:37:28
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 1,567 bytes
コンパイル時間 3,855 ms
コンパイル使用メモリ 289,276 KB
実行使用メモリ 23,296 KB
最終ジャッジ日時 2025-04-04 21:39:37
合計ジャッジ時間 9,819 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define LB(v, x) (int)(lower_bound(ALL(v), x) - (v).begin())
#define UQ(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define IO ios::sync_with_stdio(false), cin.tie(nullptr);
#define chmax(a, b) (a) = (a) < (b) ? (b) : (a)
#define chmin(a, b) (a) = (a) < (b) ? (a) : (b)
using namespace std;
using ll = long long;
const int INF = 1e9 + 10;
const ll INFL = 4e18;

int main() {
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
    vector<int> b1;
    for (int i = 0; i < N; i++)
        if (B[i] == 1) b1.push_back(i);

    vector<int> pre(N, -1), nxt(N, -1);
    for (int i = 0; i < N; i++) {
        if (A[i] == 1) {
            nxt[i + 1] = i, pre[i] = i + 1;
        } else if (B[i] == 2) {
            int nb = b1[LB(b1, i + 1)];
            nxt[nb] = i, pre[i] = nb;
        }
    }

    vector<bool> seen(N, false);
    map<int, vector<int>> ans;
    for (int i = 0; i < N; i++) {
        if (seen[i]) continue;
        if (pre[i] == -1) {
            ans[i].push_back({i});
        } else {
            int now = i;
            while (pre[now] != -1) now = pre[now];
            int top = now;
            vector<int> out;
            while (true) {
                out.push_back(now);
                seen[now] = true;
                now = nxt[now];
                if (now == -1) break;
            }
            ans[top] = out;
        }
    }
    for (auto [x, v] : ans) {
        for (int y : v) cout << y + 1 << '\n';
    }
}
0