結果

問題 No.470 Inverse S+T Problem
ユーザー furafura
提出日時 2020-10-21 19:57:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,955 bytes
コンパイル時間 1,883 ms
コンパイル使用メモリ 199,972 KB
最終ジャッジ日時 2025-01-15 12:17:25
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16 WA * 7 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int V_MAX=2*52;

int n,deg[V_MAX];
vector<int> G[V_MAX];

int ans;
bool used[V_MAX],vans[V_MAX];
bool vis[V_MAX];

void dfs(int u,int curr){
	int rem=count(vis+u,vis+n,false);
	if(curr+rem<=ans) return;

	if(ans<curr){
		ans=curr;
		rep(v,n) vans[v]=used[v];
	}

	if(rem==0) return;
	if(vis[u]){ dfs(u+1,curr); return; }

	{ // 頂点 u を使う
		bool tmp[V_MAX];
		rep(v,n) tmp[v]=vis[v];
		for(int v:G[u]) deg[v]--, vis[v]=true;
		vis[u]=true;
		used[u]=true;
		dfs(u+1,curr+1);
		used[u]=false;
		for(int v:G[u]) deg[v]++;
		rep(v,n) vis[v]=tmp[v];
	}
	if(deg[u]>1){ // 頂点 u を使わない
		vis[u]=true;
		dfs(u+1,curr);
		vis[u]=false;
	}
}

int get_index(char c){
	if(c<='A' && c<='Z') return c-'A';
	else                 return 26+(c-'a');
}

int main(){
	int n; cin>>n;
	vector<string> str(n);
	rep(i,n) cin>>str[i];

	if(n>52){
		puts("Impossible");
		return 0;
	}

	vector<int> a(n),b(n),c(n);
	rep(i,n){
		a[i]=get_index(str[i][0]);
		b[i]=get_index(str[i][1]);
		c[i]=get_index(str[i][2]);
	}

	rep(i,n){
		G[2*i].emplace_back(2*i+1);
		G[2*i+1].emplace_back(2*i);
		for(int j=i+1;j<n;j++){
			if(a[i]==a[j] || (b[i]==b[j] && c[i]==c[j])){
				G[2*i].emplace_back(2*j);
				G[2*j].emplace_back(2*i);
			}
			if(c[i]==c[j] || (a[i]==a[j] && b[i]==b[j])){
				G[2*i+1].emplace_back(2*j+1);
				G[2*j+1].emplace_back(2*i+1);
			}
			if(a[i]==c[j] || (b[i]==a[j] && c[i]==b[j])){
				G[2*i].emplace_back(2*j+1);
				G[2*j+1].emplace_back(2*i);
			}
			if(c[i]==a[j] || (a[i]==b[j] && b[i]==c[j])){
				G[2*i+1].emplace_back(2*j);
				G[2*j].emplace_back(2*i+1);
			}
		}
	}

	::n=2*n;
	rep(u,n) deg[u]=G[u].size();
	dfs(0,0);
	if(ans<n){
		puts("Impossible");
		return 0;
	}

	rep(i,n){
		if(vans[2*i]){
			printf("%c %c%c\n",str[i][0],str[i][1],str[i][2]);
		}
		else{
			printf("%c%c %c\n",str[i][0],str[i][1],str[i][2]);
		}
	}

	return 0;
}
0