結果

問題 No.470 Inverse S+T Problem
ユーザー 東前頭十一枚目東前頭十一枚目
提出日時 2019-10-11 11:14:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,606 bytes
コンパイル時間 2,064 ms
コンパイル使用メモリ 186,080 KB
実行使用メモリ 6,772 KB
最終ジャッジ日時 2023-08-24 01:37:14
合計ジャッジ時間 3,789 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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))
		{}
	inline int NOT(int A) {
		return (A + V) % (2 * V);
	}
	// A -> B <=> not B -> not A
	inline void addIF(int A, bool Apos, int B, bool Bpos) {
		if(not Apos) A = NOT(A);
		if(not Bpos) B = NOT(B);
		scc.addEdge(A, B); // A -> B
		scc.addEdge(NOT(B), NOT(A)); // not B -> not A
	}
	// A <=> (not A -> A)
	void addUNARY(int A, bool Apos) {
		addIF(A, not Apos, A, Apos); // not A -> A
	}
	// A or B <=> not A -> B
	void addOR(int A, bool Apos, int B, bool Bpos) {
		addIF(A, not Apos, B, not Bpos); // not A -> B
	}
	// not(A and B) => A -> not B
	void addNAND(int A, bool Apos, int B, bool Bpos) {
		addIF(A, Apos, B, not Bpos); // A -> not B
	}
	// A xor B <=> not(A and B) and not(not A and not B)
	void addXOR(int A, bool Apos, int B, bool Bpos) {
		addNAND(A, Apos, B, Bpos); // not(A and B)
		addNAND(A, not Apos, B, not Bpos); // not(not A and not B)
	}
	// not(A xor B) <=> A xor not B
	void addXNOR(int A, bool Apos, int B, bool Bpos) {
		addXOR(A, Apos, B, not Bpos); // A xor not B
	}
	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));
				if(st.size() < 4) {
					sat.addNAND(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