結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー 0w1
提出日時 2019-05-17 02:26:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 3,249 bytes
コンパイル時間 2,122 ms
コンパイル使用メモリ 213,196 KB
最終ジャッジ日時 2025-01-07 03:42:08
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

class Twosat {
 private:
  void dfs_topo(int u, vector<int> &stk, vector<int> &vis) {
    for (int v : g[u]) {
      if (vis[v]) continue;
      vis[v] = 1;
      dfs_topo(v, stk, vis);
    }
    stk.emplace_back(u);
  }
  void dfs_ksrj(int u, vector<int> &scc, int scc_id) {
    for (int v : rg[u]) {
      if (scc[v]) continue;
      scc[v] = scc_id;
      dfs_ksrj(v, scc, scc_id);
    }
  }
 public:
  int n;
  vector<vector<int>> g, rg;
  Twosat(int _n) : n(_n), g(_n * 2), rg(_n * 2) {}
  int negate(int u) { return u < n ? n + u : u - n; }
  void if_then(int a, int b) {
    g[a].push_back(b);
    rg[b].push_back(a);
  }
  void either(int a, int b) {
    if_then(a, negate(b));
    if_then(b, negate(a));
    if_then(negate(a), b);
    if_then(negate(b), a);
  }
  void either_or_none(int a, int b) {
    if_then(a, negate(b));
    if_then(b, negate(a));
  }
  void assure(int a) { if_then(negate(a), a); }
  vector<bool> solve() {
    int scc_cnt = 0;
    vector<int> stk;
    vector<int> scc(n * 2);
    vector<int> vis(n * 2);
    for (int i = 0; i < n * 2; ++i) {
      if (vis[i]) continue;
      vis[i] = 1;
      dfs_topo(i, stk, vis);
    }
    for (int i = n * 2 - 1; ~i; --i) {
      if (scc[stk[i]]) continue;
      scc[stk[i]] = ++scc_cnt;
      dfs_ksrj(stk[i], scc, scc_cnt);
    }
    for (int i = 0; i < n; ++i) {
      if (scc[i] == scc[n + i]) {
        return {}; // no solution
      }
    }
    vector<int> sat(scc_cnt + 1);
    for (int i = n * 2 - 1; ~i; --i) {
      int u = stk[i];
      int v = negate(u);
      if (sat[scc[u]]) {
        sat[scc[v]] = 3 - sat[scc[u]];
      } else if (sat[scc[v]]) {
        sat[scc[u]] = 3 - sat[scc[v]];
      } else {
        sat[scc[u]] = 2;
        sat[scc[v]] = 1;
      }
    }
    vector<bool> sol(n);
    for (int i = 0; i < n; ++i) {
      sol[i] = sat[scc[i]] & 1;
    }
    return sol;
  }
};

signed main() {
  int N;
  cin >> N;

  vector<string> S(N);
  for (int i = 0; i < N; ++i) {
    cin >> S[i];
  }

  if (52 < N) {
    cout << "Impossible" << endl;
  } else {
    Twosat solver(N);
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        if (i == j) continue;
        if (S[i].substr(0, 1) == S[j].substr(0, 1) || S[i].substr(1, 2) == S[j].substr(1, 2)) {
          solver.either_or_none(i, j);
        }
        if (S[i].substr(0, 2) == S[j].substr(0, 2) || S[i].substr(2, 1) == S[j].substr(2, 1)) {
          solver.either_or_none(solver.negate(i), solver.negate(j));
        }
        if (S[i].substr(0, 1) == S[j].substr(2, 1) || S[i].substr(1, 2) == S[j].substr(0, 2)) {
          solver.either_or_none(i, solver.negate(j));
        }
        if (S[i].substr(0, 2) == S[j].substr(1, 2) || S[i].substr(2, 1) == S[j].substr(0, 1)) {
          solver.either_or_none(solver.negate(i), j);
        }
      }
    }
    vector<bool> sol = solver.solve();
    if (sol.empty()) {
      cout << "Impossible" << endl;
    } else {
      for (int i = 0; i < N; ++i) {
        if (sol[i]) {
          cout << S[i].substr(0, 1) << " " << S[i].substr(1, 2) << endl;
        } else {
          cout << S[i].substr(0, 2) << " " << S[i].substr(2, 1) << endl;
        }
      }
    }
  }

  return 0;
}
0