結果

問題 No.470 Inverse S+T Problem
ユーザー furafura
提出日時 2020-10-21 19:57:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,955 bytes
コンパイル時間 2,193 ms
コンパイル使用メモリ 205,624 KB
実行使用メモリ 8,760 KB
最終ジャッジ日時 2023-08-24 01:41:44
合計ジャッジ時間 6,359 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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