結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー Kutimoti_T
提出日時 2018-05-08 22:49:15
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,136 bytes
コンパイル時間 1,895 ms
コンパイル使用メモリ 179,052 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-22 13:49:56
合計ジャッジ時間 3,179 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 19 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

int N;
vector<string> u;

#include <algorithm>
#include <bitset>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64, i64> P;

vector<int> sccd(const vector<vector<int>> & G){
  vector<vector<int>> rG(G.size());
  for(int i = 0;i < G.size();i++){
    for(int to : G[i]) rG[to].push_back(i);
  }

  vector<bool> vis(G.size(),false);
  vector<int> vs;
  vector<int> res(G.size(),-1);

  function<void(int)> dfs = [&](int v){
    vis[v] = true;
    for(int to : G[v]){
      if(!vis[to]) dfs(to);
    }
    vs.push_back(v);
  };

  function<void(int,int)> rdfs = [&](int v,int k){
    vis[v] = true;
    res[v] = k;
    for(int to : rG[v]){
      if(!vis[to]) rdfs(to,k);
    }
  };

  for(int i = 0;i < G.size();i++){
    if(!vis[i]) dfs(i);
  }

  vis.assign(G.size(),false);
  int k = 0;
  for(int i = 0;i < G.size();i++){
    if(!vis[vs[i]]) rdfs(vs[i],k++);
  }
  return res;
}

int main(){
  cin >> N;
  u.resize(N);
  if(N > 52){
    cout << "Impossible" << endl;
    return 0;
  }
  rep(i,0,N - 1){
    cin >>  u[i];
  }

  vector<vector<int>> G(N * 2);

  rep(i,0,N - 1){
    rep(j,i + 1,N - 1){
      rep(k,0,1){
        rep(l,0,1){
          string s2 = u[i].substr(k,2);
          string s1 = u[i].substr((1 - k) * 2,1);
          string t2 = u[j].substr(l,2);
          string t1 = u[j].substr((1 - l) * 2,1);
          if(s2 == t2 || s1 == t1){
            G[i + N * k].push_back(j + N * (1 - l));
            G[j + N * l].push_back(i + N * (1 - k));
          }
        }
      }
    }
  }

  auto res = sccd(G);

  rep(i,0,N - 1){
    if(res[i] == res[i + N]){
      cout << "Impossible" << endl;
      return 0;
    }
  }

  rep(i,0,N - 1){
    string s1,s2;
    if(res[i] > res[i + N]){
      s1 = u[i].substr(0,2);
      s2 = u[i].substr(2,1);
    }
    else{
      s1 = u[i].substr(0,1);
      s2 = u[i].substr(1,2);
    }

    cout << s1 << " " << s2 << endl;
  }
}
0