結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー 303Yuyu
提出日時 2021-03-18 11:03:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,980 bytes
コンパイル時間 5,068 ms
コンパイル使用メモリ 242,076 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-22 14:05:19
合計ジャッジ時間 5,360 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using ld = long double;
using vld = vector<ld>;
using vb = vector<bool>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define dbg(x) true
#endif

template <class T> bool chmin(T& a, T b) {
    if(a > b) { a = b; return true; }
    else return false;
}

template <class T> bool chmax(T& a, T b) {
    if(a < b) { a = b; return true; }
    else return false;
}

template <class T> ostream& operator<<(ostream& s, const vector<T>& a) {
    for(auto i : a) s << i << ' ';
    return s;
}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 62;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

struct SCC {
    using Graph = vector<vector<int>>;
    int V;
    Graph g, rg;    // rgは逆向きのグラフ
    vector<int> post_order, tmp;
    vector<bool> seen;
    SCC(int V) : V(V), g(V), rg(V) {};

    void add_edge(int u, int v) {
        g[u].push_back(v);
        rg[v].push_back(u);
    }

    // 後行順に探索した結果を求める
    void dfs_post(int v) {
        seen[v] = true;
        for(int nv : g[v]) {
            if(seen[nv]) continue;
            dfs_post(nv);
        }
        post_order.push_back(v);
    }

    // 各連結成分を求める
    void dfs_scc(int v) {
        seen[v] = true;
        tmp.push_back(v);
        for(int nv : rg[v]) {
            if(seen[nv]) continue;
            dfs_scc(nv);
        }
    }

    // res[i]は同じ連結成分の頂点の集合
    vector<vector<int>> scc() {
        // 後行順を逆に並べる。DFSで探索できる先の頂点ほど前に来る
        seen.assign(V, false);
        for(int i = 0; i < V; ++i) {
            if(seen[i]) continue;
            dfs_post(i);
        }
        reverse(post_order.begin(), post_order.end());

        // 移動先の頂点から逆向きグラフで移動できる頂点は強連結となる
        vector<vector<int>> res;
        seen.assign(V, false);
        for(int i = 0; i < V; ++i) {
            int v = post_order[i];
            if(seen[v]) continue;
            tmp.clear();
            dfs_scc(v);
            res.push_back(tmp);
        }
        return res;
    }
};

struct TwoSat {
    int n;
    SCC s;  // 0~n-1はtrue, n~2n-1はfalse
    vector<int> cmp;
    TwoSat(int n) : n(n), s(2*n), cmp(2*n) {};

    // (Xi=f or Xj=g)のクロージャを追加
    void add_clause(int i, bool f, int j, bool g) {
        int ni = i, nj = j; // (i,f),(j,g)の否定
        if(!f) i += n;
        if(!g) j += n;
        if(f) ni += n;
        if(g) nj += n;
        s.add_edge(ni, j);
        s.add_edge(nj, i);
    }

    // 条件を満たす割当が存在するか判定
    bool satisfable() {
        auto scc = s.scc();
        int sz = scc.size();
        for(int i = 0; i < sz; ++i) {
            for(auto j : scc[i]) cmp[j] = i;
        }
        for(int i = 0; i < n; ++i) {
            // 同じ連結成分にいるため割当は存在しない
            if(cmp[i] == cmp[i+n]) return false;
        }
        return true;
    }

    // クローズを満たす割当を返す
    vector<bool> answer() {
        vector<bool> res(n);
        for(int i = 0; i < n; ++i) {
            // ^X=>Xを満たすためにはX=true
            if(cmp[i] > cmp[i+n]) res[i] = true;
        }
        return res;
    }
};

// https://yukicoder.me/problems/no/470
void solve() {
    ll n;
    cin >> n;
    if(n > 52) {
        cout << "Impossible" << endl;
        return;
    }

    vector<string> u(n);
    rep(i, n) cin >> u[i];

    TwoSat ts(n);

    for(int i = 0; i < n; ++i) {
        for(int j = i+1; j < n; ++j) {
            if(u[i][0] == u[j][0]) ts.add_clause(i, false, j, false);
            if(u[i][0] == u[j][2]) ts.add_clause(i, false, j, true);
            if(u[i][2] == u[j][0]) ts.add_clause(i, true, j, false);
            if(u[i][2] == u[j][2]) ts.add_clause(i, true, j, true);
            if(u[i].substr(1, 2) == u[j].substr(1, 2)) ts.add_clause(i, false, j, false);
            if(u[i].substr(1, 2) == u[j].substr(0, 2)) ts.add_clause(i, false, j, true);
            if(u[i].substr(0, 2) == u[j].substr(1, 2)) ts.add_clause(i, true, j, false);
            if(u[i].substr(0, 2) == u[j].substr(0, 2)) ts.add_clause(i, true, j, true);
        }
    }

    if(!ts.satisfable()) {
        cout << "Impossible" << endl;
    }
    else {
        vb ans = ts.answer();
        rep(i, n) { 
            if(ans[i]) cout << u[i][0] << ' ' << u[i].substr(1, 2) << endl;
            else cout << u[i].substr(0, 2) << ' ' << u[i][2] << endl;
        }
    }
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}
0