結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー tossy
提出日時 2017-06-06 15:44:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 3,134 bytes
コンパイル時間 2,599 ms
コンパイル使用メモリ 195,676 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2024-12-22 13:43:54
合計ジャッジ時間 3,496 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 2147483600

// Strongly Connected Components O(E + V)
class SCC {
private:
  vector<vector<int>> &G;
  vector<vector<int>> &rG;
  vector<bool> used;
  vector<int> vs;
  vector<int> cmp; // 頂点iが属するSCCのID
  int n;
  void dfs(int v){
    used[v] = true;
    for(auto to : G[v]) if(!used[to]) dfs(to);
    vs.pb(v);
  }
  void rdfs(int v, int k){
    used[v] = true;
    cmp[v] = k;
    for(auto to : rG[v]) if(!used[to]) rdfs(to, k);
  }
public:
  int gc = 0; // group count
  SCC(vector<vector<int>> &g, vector<vector<int>> &r) : G(g), rG(r){
    n = G.size();
    used = vector<bool>(n,false);
    cmp.resize(n);
    rep(i,n) if(!used[i]) dfs(i);
    fill(all(used), false);
    for(int i = vs.size()-1; i>=0; i--) if(!used[vs[i]]) rdfs(vs[i], gc++);
  }
  inline bool same(int i, int j){ return cmp[i]==cmp[j]; }
  inline int operator[](int i){ return cmp[i]; }
};

// 2-SAT O(M + N) M:# of vars, N:# of clauses
class TwoSat {
private:
  vector<vector<int> > vec;
  vector<vector<int> > rev;
  vector<bool> res;
  int v;
public:
  TwoSat(int n) : v(n){
    vec.resize(2*v);
    rev.resize(2*v);
    res.resize(v);
  }
  inline void add_edge(int a, bool ab, int b, bool bb){
    // add (a -> b)
    int va = a + (ab?0:v);
    int vb = b + (bb?0:v);
    vec[va].pb(vb);
    rev[vb].pb(va);
  }
  inline void add(int a, bool ab, int b, bool bb){
    // a or b <-> ((!a -> b) and (!b -> a))
    add_edge(a, !ab, b, bb);
    add_edge(b, !bb, a, ab);
  }
  bool exec(){
    SCC scc(vec, rev);
    rep(i,v){
      if(scc.same(i, i+v)) return false;
      res[i] = scc[i]>scc[i+v];
    }
    return true;
  }
  inline int operator[](int i){ return res[i]; }
};


bool solve(){
  int n;
  cin>>n;
  vector<string> vec(n);
  rep(i,n) cin>>vec[i];

  if(n > 52) return false;

  map<string, vector<int>> m;
  TwoSat sat(2*n);
  // 2*i:iを前で切る，2*i+1:iを後ろで切る
  rep(i,n) sat.add(2*i,true,2*i+1,true);

  rep(i,n){
    m[vec[i].substr(0,1)].pb(2*i);
    m[vec[i].substr(1,2)].pb(2*i);
    m[vec[i].substr(0,2)].pb(2*i+1);
    m[vec[i].substr(2,1)].pb(2*i+1);
  }

  for(auto &p : m){
    auto &v = p.second;
    int l=v.size();
    rep(i,l)rep(j,l)if(i!=j) sat.add_edge(v[i],true,v[j],false);
  }

  if(!sat.exec()) return false;

  rep(i,n){
    if(sat[2*i]) cout << vec[i].substr(0,1) << " " << vec[i].substr(1,2) << endl;
    else cout << vec[i].substr(0,2) << " " << vec[i].substr(2,1) << endl;
  }

  return true;
}

int main(){
  if(!solve()) cout << "Impossible" << endl;

  return 0;
}
0