結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー 🐬hec
提出日時 2017-05-14 13:47:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,383 bytes
コンパイル時間 2,427 ms
コンパイル使用メモリ 194,220 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-22 13:43:41
合計ジャッジ時間 3,885 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 17 WA * 9 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0;}
template<class T>bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0;}

using ll = long long;
using R = long double;
const R EPS = 1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r) {return (r > EPS) - (r < -EPS);}
inline R sq(R x) {return sqrt(max(x, 0.0L));}

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

// Problem Specific Parameter:
#define error(args...) {}
//{ vector<string> _debug = split(#args, ',');err(begin(_debug), args);}

vector<string> split(const string& s, char c) {
	vector<string> v; stringstream ss(s); string x;
	while (getline(ss, x, c)) v.emplace_back(x);
	return move(v);
}

void err(vector<string>::iterator it) {cerr << endl;}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args) {
	cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << " ", err(++it, args...);
}


// Description: 2-SAT
// Verifyed: Many Diffrent Problem
// Required: 有向グラフに対する強連結成分

//Appropriately Changed
using edge = struct {int to;};
using G = vector<vector<edge>>;

//Appropriately Changed
void add_edge(G &graph, int from, int to) {
	error(from, to);
	graph[from].push_back({to});
}

// Description: 有向グラフに対する強連結成分
// TimeComplexity: $ \mathcal{O}(V + E) $
// Verifyed: AOJ GRL_3_C

auto strongly_connected_components(const G& graph,vector<int> &topolgy) {
	int n = graph.size(), k = 0;
	vector<int> par(n), ord(n, -1), low(n), scc(n, -1), res;
	stack<int> s;

	auto dfs = [&](int v, int p, int &k) {
		auto func = [&](int v, int p, int &k, auto func)->void{
			ord[v] = k++, low[v] = ord[v], par[v] = p, s.push(v);
			for (auto &e : graph[v]) {
				if (scc[e.to] != -1) continue;
				if (ord[e.to] == -1) {
					func(e.to, v, k, func);
					chmin(low[v], low[e.to]);
				} else
					chmin(low[v], ord[e.to]);
			}
			if (ord[v] != low[v]) return ;
			while (1) {
				int u = s.top(); s.pop();
				scc[u] = v;
				if (u == v) break;
			}
		};
		return func(v, p, k, func);
	};

	for(auto &v:topolgy) if (ord[v] == -1) dfs(v, -1, k);
	return make_tuple(scc, ord);
}

// Description: 有向グラフに対するトポロジカルソート  
// TimeComplexity: $ \mathcal{O}(V + E) $
// Verifyed: AOJ GRL_4_B
 
auto topological_sort(const G& graph){
    const int n=graph.size();
    vector<int> used(n,0),order;

    auto dfs=[&](int v){
        auto func=[&](int v,auto func)->void{
            used[v]=true;
            for(auto &e:graph[v]) if(!used[e.to]) func(e.to,func);
            order.push_back(v);
        };
        return func(v,func);
    };
    
    rep(v,n)if(!used[v]) dfs(v);
    reverse(_all(order));
    return order;
}

// x&1 == 1 True
// x&1 == 0 False
void closure_or(G &graph, int a, int b) {
	add_edge(graph, a ^ 1, b);
	add_edge(graph, b ^ 1, a);
}

auto get_variable(G &graph) {
	const int n = graph.size() / 2;
	vector<int> ret(n, 0);

	vector<int> topolgy = topological_sort(graph);
	vector<int> scc, ord;
	tie(scc, ord) = strongly_connected_components(graph,topolgy);
	rep(i, 2 * n) error(scc[i], ord[i]);

	rep(i, n) {
		if (scc[2 * i] == scc[2 * i + 1])
			ret[0] = -1;
		else {
			// F -> T というトポロジカル順序
			// 理由 F を満たすと、Tを満たすとなるためアウト
			ret[i] = (scc[2 * i + 1] >  scc[2 * i]);
		}
	}
	return ret;
}


string s[1010];

int main(void) {
	int n;
	cin >> n;

	const int limit = 52;

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

	rep(i, n) cin >> s[i];

	G graph(2 * n);

	// F a | bc
	// T ab | c
	rep(i, n)rep(j, i) {
		// F F
		if (s[i].substr(0, 1) == s[j].substr(0, 1) or s[i].substr(1, 2) == s[j].substr(1, 2)) {
			error(i, "F", j, "F");
			closure_or(graph, 2 * i + 1, 2 * j + 1);
		}

		// T F
		if (s[i].substr(2, 1) == s[j].substr(0, 1) or s[i].substr(0, 2) == s[j].substr(1, 2)) {
			error(i, "T", j, "F");
			closure_or(graph, 2 * i, 2 * j + 1);
		}

		// F T
		if (s[i].substr(0, 1) == s[j].substr(2, 1) or s[i].substr(1, 2) == s[j].substr(0, 2)) {
			error(i, "F", j, "T");
			closure_or(graph, 2 * i + 1, 2 * j);
		}

		// T T
		if (s[i].substr(2, 1) == s[j].substr(2, 1) or s[i].substr(0, 2) == s[j].substr(0, 2)) {
			error(i, "T", j, "T");
			closure_or(graph, 2 * i, 2 * j);
		}
	}

	vector<int> ret = get_variable(graph);

	if (ret[0] == -1) {
		puts("Impossible");
		return 0;
	}


	rep(i, n) {
		error(ret[i]);
		if (ret[i])
			cout << s[i][0] << s[i][1] << " " << s[i][2] << endl;
		else
			cout << s[i][0] << " " << s[i][1] << s[i][2] << endl;
	}

	return 0;
}
0