#1169543 (C++14) No.470 Inverse S+T Problem

• 問題: No.470 Inverse S+T Problem
• ユーザー: 梧桐
• 提出日時: 2026-06-21 23:48:14
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 3,159 bytes
• コンパイル時間: 1,514 ms
• コンパイル使用メモリ: 84,428 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-06-21 23:48:19
• 合計ジャッジ時間: 2,700 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

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

ソースコード

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>

using namespace std;

const int N = 110, M = 50010;

int n;
string s[N];

int h[N], e[M], ne[M], idx;
int dfn[N], low[N], scc[N], scc_idx, ts;
stack<int> stk;
bool in_stk[N];

void Add(int x, int y) {
    e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}

char Single(int a, int v) {
    return v ? s[a][0] : s[a][2];
}

string Pair(int a, int v) {
    return v ? s[a].substr(1, 2) : s[a].substr(0, 2);
}

// 禁止「x_a = va 且 x_b = vb」同时成立：(¬(x_a=va) ∨ ¬(x_b=vb))
void Forbid(int a, int va, int b, int vb) {
    Add(a + va * n, b + !vb * n);
    Add(b + vb * n, a + !va * n);
}
    
void Tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    in_stk[u] = true;
    stk.push(u);
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            Tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (in_stk[j]) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    if (low[u] == dfn[u]) {
        ++scc_idx;
        while (true) {
            int v = stk.top(); stk.pop();
            in_stk[v] = false;
            scc[v] = scc_idx;
            if (u == v) break;
        }
    }
}

/**
 * 每个长度为 3 的串 $U_i=c_0c_1c_2$ 只有两种切法：
 *   切法 A（$1+2$）：单字母 $c_0$，双字母 $c_1c_2$
 *   切法 B（$2+1$）：单字母 $c_2$，双字母 $c_0c_1$
 *
 * 长度 1 与长度 2 的串永不相等，故「$2N$ 个串互不相同」等价于：
 *   所有单字母互不相同 + 所有双字母互不相同。
 * 单字母只有 52 个，$N\ge 53$ 时鸽巢必撞 $\Rightarrow$ Impossible。
 *
 * 每个 $i$ 是二选一开关 $x_i$（$1$ 选 A，$0$ 选 B）。
 * 两物品若某组合让单字母或双字母相同即冲突，转成「不能同时」的二元子句，
 * 即 2-SAT。节点 $i$ 表 $x_i=0$，$i+n$ 表 $x_i=1$；
 * Tarjan 缩点后判 $scc[i]=scc[i+n]$ 无解，否则按 $scc[i]>scc[i+n]$ 还原取值。
 *
 * 复杂度：$O(N^2)$ 建边 + Tarjan $O(N^2)$，$N\le 52$。
 */

int main() {
    // freopen("st.in", "r", stdin);
    // freopen("st.out", "w", stdout);

    cin >> n;

    if (n >= 53) {
        puts("Impossible");
        return 0;
    }

    memset(h, -1, sizeof(h));
    for (int i = 1; i <= n; ++i) cin >> s[i];

    for (int a = 1; a <= n; ++a) {
        for (int b = a + 1; b <= n; ++b) {
            for (int va = 0; va <= 1; ++va) {
                for (int vb = 0; vb <= 1; ++vb) {
                    if (Single(a, va) == Single(b, vb) || Pair(a, va) == Pair(b, vb)) {
                        Forbid(a, va, b, vb);
                    }
                }
            }
        }
    }

    for (int i = 1; i <= 2 * n; ++i) if (!dfn[i]) Tarjan(i);
    for (int i = 1; i <= n; ++i) {
        if (scc[i] == scc[i + n]) {
            puts("Impossible");
            return 0;
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (scc[i] > scc[i + n]) {
            cout << s[i][0] << ' ' << s[i].substr(1) << '\n';
        } else {
            cout << s[i].substr(0, 2) << ' ' << s[i][2] << '\n';
        }
    }

    return 0;
}