#1151037 (C++23) No.470 Inverse S+T Problem

• 問題: No.470 Inverse S+T Problem
• ユーザー: rabimea
• 提出日時: 2026-03-02 14:53:56
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 6 ms / 2,000 ms
• コード長: 3,155 bytes
• コンパイル時間: 4,189 ms
• コンパイル使用メモリ: 361,800 KB
• 実行使用メモリ: 7,972 KB
• 最終ジャッジ日時: 2026-03-02 14:54:01
• 合計ジャッジ時間: 3,777 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
sample	AC * 4
other	AC * 27

ソースコード

#include <bits/stdc++.h>

#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
using std::cin, std::cout, std::cerr;
using ll = long long;

struct Scc {
    int n;
    std::vector<std::vector<int>> e, e2;
    std::vector<int> vis, scc;
    std::vector<int> v;
    int cnt;

    int& operator [](int i) { return scc[i]; }

    void Dfs1(int x) {
        vis[x] = 1;
        for(int i : e[x]) if(!vis[i]) Dfs1(i);
        v.push_back(x);
    }
    void Dfs2(int x, int id) {
        scc[x] = id;
        for(int i : e2[x]) if(!scc[i]) Dfs2(i, id);
    }
    void Kosaraju(int n, std::vector<std::vector<int>> e) {
        this->n = n;
        this->e = e;
        e2.assign(n + 1, {});
        vis.assign(n + 1, 0);
        scc.assign(n + 1, 0);
        v.clear();
        rep(i, 1, n) for(int x : e[i])
            e2[x].push_back(i);
        rep(i, 1, n) if(!vis[i]) Dfs1(i);
        std::ranges::reverse(v);
        cnt = 0;
        for(int x : v) if(!scc[x]) Dfs2(x, ++cnt);
    }

    std::vector<std::vector<int>> Contract() {
        std::vector<std::vector<int>> ne(cnt + 1);
        rep(i, 1, n)
            for(int x : e[i])
                if(scc[i] != scc[x])
                    ne[scc[i]].push_back(scc[x]);
        rep(i, 1, cnt) {
            std::ranges::sort(ne[i]);
            ne[i].erase(std::unique(ne[i].begin(), ne[i].end()), ne[i].end());
        }
        return ne;
    }
};

void Solve() {
    int n; cin >> n;
    std::vector<std::string> s(n + 1);
    rep(i, 1, n) cin >> s[i];

    if(n > 52) {
        cout << "Impossible\n";
        return;
    }

    std::vector<std::vector<int>> e(2 * n + 1);
    rep(i, 1, n) rep(j, 1, n) if(i != j) {
        std::string li0 = s[i].substr(0, 1), li1 = s[i].substr(1, 2);
        std::string ri0 = s[i].substr(0, 2), ri1 = s[i].substr(2, 1);

        std::string lj0 = s[j].substr(0, 1), lj1 = s[j].substr(1, 2);
        std::string rj0 = s[j].substr(0, 2), rj1 = s[j].substr(2, 1);

        if(li0 == lj0 || li1 == lj1) {
            e[2 * i - 1].push_back(2 * j);
            e[2 * j - 1].push_back(2 * i);
        }
        if(ri0 == rj0 || ri1 == rj1) {
            e[2 * i].push_back(2 * j - 1);
            e[2 * j].push_back(2 * i - 1);
        }

        if(li0 == rj1 || li1 == rj0) {
            e[2 * i - 1].push_back(2 * j - 1);
            e[2 * j].push_back(2 * i);
        }
        if(ri0 == lj1 || ri1 == lj0) {
            e[2 * i].push_back(2 * j);
            e[2 * j - 1].push_back(2 * i - 1);
        }
    }
    Scc scc;
    scc.Kosaraju(2 * n, e);

    // rep(i, 1, 2 * n) {
    //     std::set<int> set;
    //     for(int x : e[i]) set.insert(x);
    //     for(int x : set) cout << i << ' ' << x << '\n';
    // }

    rep(i, 1, n) if(scc[2 * i - 1] == scc[2 * i]) {
        cout << "Impossible\n";
        return;
    }

    rep(i, 1, n) {
        if(scc[2 * i - 1] > scc[2 * i]) {
            cout << s[i][0] << ' ' << s[i][1] << s[i][2] << '\n';
        } else {
            cout << s[i][0] << s[i][1] << ' ' << s[i][2] << '\n';
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    int T = 1;
    while(T --) {
        Solve();
    }
}