結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー zengyongxu-jerry
提出日時 2026-06-24 21:45:45
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 2,783 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,684 ms
コンパイル使用メモリ 338,216 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2026-06-24 21:45:52
合計ジャッジ時間 4,563 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
const int N = 2e5 + 5, M = 1e6 + 5;
const int inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int n, m;
int head[N], idx;
int dfn[N], low[N], tot;
int bel[N], scc, stk[N], tp;
bool ins[N];
struct edge{
	int to, nxt;
} e[M << 1];
string s[N];

void add(int u, int v){
	e[++ idx] = {v, head[u]}, head[u] = idx;
}
void Tarjan(int u){
    dfn[u] = low[u] = ++ tot;
    ins[u] = true, stk[++ tp] = u;
    
    for (int i = head[u]; ~i; i = e[i].nxt){
        int v = e[i].to;
        if (!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    
    if (dfn[u] == low[u]){
        scc ++;
        
        int now;
        do{
            now = stk[tp -- ];
            ins[now] = false;
            bel[now] = scc;
        } while (now != u);
    }
}

void init(){
	idx = -1;
	memset(head, -1, sizeof head);
}
void solve(){
	cin >> n;
	if (n > 52){
		cout << "Impossible\n";
		return ;
	}
	
	for (int i = 1; i <= n; i ++ ) cin >> s[i];
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= n; j ++ ){
			if (i == j) continue;
			{
				string a; a += s[i][0];
				string b; b += s[i][1], b += s[i][2];
				string c; c += s[j][0];
				string d; d += s[j][1], d += s[j][2];
				if (a == b || a == c || a == d || b == c || b == d || c == d) add(2 * i, 2 * j - 1), add(2 * j, 2 * i - 1);
			}
			{
				string a; a += s[i][0];
				string b; b += s[i][1], b += s[i][2];
				string c; c += s[j][0], c += s[j][1];
				string d; d += s[j][2];
				if (a == b || a == c || a == d || b == c || b == d || c == d) add(2 * i, 2 * j), add(2 * j - 1, 2 * i - 1);
			}
			{
				string a; a += s[i][0], a += s[i][1];
				string b; b += s[i][2];
				string c; c += s[j][0];
				string d; d += s[j][1], d += s[j][2];
				if (a == b || a == c || a == d || b == c || b == d || c == d) add(2 * i - 1, 2 * j - 1), add(2 * j, 2 * i);
			}
			{
				string a; a += s[i][0], a += s[i][1];
				string b; b += s[i][2];
				string c; c += s[j][0], c += s[j][1];
				string d; d += s[j][2];
				if (a == b || a == c || a == d || b == c || b == d || c == d) add(2 * i - 1, 2 * j), add(2 * j - 1, 2 * i);
			}
		}
	for (int i = 1; i <= n + n; i ++ ) if (!dfn[i]) Tarjan(i);
	
	for (int i = 1; i <= n; i ++ ){
		if (bel[i * 2 - 1] == bel[i * 2]){
			cout << "Impossible\n";
			return ;
		}
	}
	
	for (int i = 1; i <= n; i ++ ){
		if (bel[i * 2 - 1] < bel[i * 2]) cout << s[i][0] << s[i][1] << " " << s[i][2] << "\n";
		else cout << s[i][0] << " " << s[i][1] << s[i][2] << "\n";
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T = 1; //cin >> T;
	while (T -- ) init(), solve();
}
0