結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー 東前頭十一枚目
提出日時 2019-10-03 16:01:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 2,901 bytes
コンパイル時間 2,280 ms
コンパイル使用メモリ 186,780 KB
実行使用メモリ 6,784 KB
最終ジャッジ日時 2024-12-22 13:54:36
合計ジャッジ時間 3,366 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct StronglyConnectedComponent {
	const int V;
	vector<vector<int>> G, revG;
	vector<int> id;
	StronglyConnectedComponent(const int V) :
		V(V),
		G(vector<vector<int>>(V, vector<int>())),
		revG(vector<vector<int>>(V, vector<int>())),
		id(vector<int>(V))
		{}
	void addEdge(int from, int to) {
		G[from].push_back(to);
		revG[to].push_back(from);
	}
	void build() {
		vector<bool> used(V, false);
		stack<int> st;
		for(int from = 0; from < V; ++from) {
			if(not used[from]) {
				dfs(from, used, st);
			}
		}
		int num = 0;
		while(st.size()) {
			int from = st.top();
			st.pop();
			if(used[from]) {
				revdfs(from, num, used);
				++num;
			}
		}
	}
	void dfs(int from, vector<bool> &used, stack<int> &st) {
		used[from] = true;
		for(int to : G[from]) {
			if(not used[to]) {
				dfs(to, used, st);
			}
		}
		st.push(from);
	}
	void revdfs(int from, int num, vector<bool> &used) {
		used[from] = false;
		id[from] = num;
		for(int to : revG[from]) {
			if(used[to]) {
				revdfs(to, num, used);
			}
		}
	}
	int get(int x) {
		return id[x];
	}
};

struct TwoSatisfiability {
	const int V;
	vector<vector<int>> G;
	vector<bool> pos;
	StronglyConnectedComponent scc;
	TwoSatisfiability(const int V) :
		V(V),
		G(vector<vector<int>>(2 * V, vector<int>())),
		pos(vector<bool>(2 * V)),
		scc(StronglyConnectedComponent(2 * V))
		{}
	// a or b
	void addEdge(int a, bool apos, int b, bool bpos) {
		if(not apos) a += V;
		if(not bpos) b += V;
		scc.addEdge((a + V) % (2 * V), b); // not a -> b
		scc.addEdge((b + V) % (2 * V), a); // not b -> a
	}
	bool solve() {
		scc.build();
		for(int i = 0; i < V; ++i) {
			if(scc.get(i) == scc.get(i + V)) {
				return false;
			}
			pos[i] = (scc.get(i) > scc.get(i + V));
		}
		return true;
	}
	bool get(int x) {
		return pos[x];
	}
};

int main() {
	int n; cin >> n;
	string u[n];
	for(int i = 0; i < n; ++i) {
		cin >> u[i];
	}
	if(n > 100) {
		cout << "Impossible" << '\n';
		return 0;
	}
	TwoSatisfiability sat(n);
	for(int i = 0; i < n; ++i) {
		for(int j = i + 1; j < n; ++j) {
			for(int mask = 0; mask < (1 << 2); ++mask) {
				bool ipos = (mask & 1);
				bool jpos = ((mask >> 1) & 1);
				int sin = 1;
				if(not ipos) {
					sin = 2;
				}
				int sjn = 1;
				if(not jpos) {
					sjn = 2;
				}
				set<string> st;
				st.insert(u[i].substr(0, sin));
				st.insert(u[i].substr(sin));
				st.insert(u[j].substr(0, sjn));
				st.insert(u[j].substr(sjn));
				// 衝突するとき
				// not (A and B)
				// => (not A) or (not B)
				if(st.size() < 4) {
					sat.addEdge(i, not ipos, j, not jpos);
				}
			}
		}
	}
	if(not sat.solve()) {
		cout << "Impossible" << '\n';
		return 0;
	}
	for(int i = 0; i < n; ++i) {
		if(sat.get(i)) {
			cout << u[i].substr(0, 1) << " " << u[i].substr(1) << '\n';
		} else {
			cout << u[i].substr(0, 2) << " " << u[i].substr(2) << '\n';
		}
	}
	return 0;
}
0