結果

問題 No.470 Inverse S+T Problem
ユーザー Kutimoti_TKutimoti_T
提出日時 2018-05-08 22:49:15
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,136 bytes
コンパイル時間 1,590 ms
コンパイル使用メモリ 178,192 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-01 22:54:56
合計ジャッジ時間 2,713 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 WA -
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 4 ms
6,272 KB
testcase_07 AC 4 ms
6,272 KB
testcase_08 AC 2 ms
6,272 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 1 ms
5,376 KB
testcase_16 WA -
testcase_17 AC 2 ms
5,376 KB
testcase_18 WA -
testcase_19 AC 1 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 1 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 1 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 1 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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