結果
| 問題 |
No.470 Inverse S+T Problem
|
| コンテスト | |
| ユーザー |
 anta
|
| 提出日時 | 2016-12-21 00:14:57 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 14 ms / 2,000 ms |
| コード長 | 6,039 bytes |
| コンパイル時間 | 2,141 ms |
| コンパイル使用メモリ | 188,092 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-12-22 13:34:54 |
| 合計ジャッジ時間 | 3,459 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 27 |
ソースコード
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }
struct StaticGraph {
typedef int Arc;
typedef pair<int, Arc> Edge;
struct ArcList {
ArcList() : arcBegin(), arcEnd() {}
ArcList(const Arc *arcBegin, const Arc *arcEnd) : arcBegin(arcBegin), arcEnd(arcEnd) {}
const Arc *begin() const { return arcBegin; }
const Arc *end() const { return arcEnd; }
int size() const { return (int)(arcEnd - arcBegin); }
bool empty() const { return arcBegin == arcEnd; }
Arc operator[](int i) const { return arcBegin[i]; }
private:
const Arc * const arcBegin, *const arcEnd;
};
int size() const { return (int)offsets.size() - 1; }
ArcList operator[](int i) const {
return ArcList(arcs.data() + offsets[i], arcs.data() + offsets[i + 1]);
}
void init(int n, const vector<Edge> &edges) {
int m = (int)edges.size();
arcs.resize(m + 1);
offsets.assign(n + 1, 0);
for (int ei = 0; ei < m; ++ei)
++offsets[edges[ei].first];
for (int i = 0; i < n; ++i)
offsets[i + 1] += offsets[i];
for (int ei = m - 1; ei >= 0; --ei)
arcs[--offsets[edges[ei].first]] = edges[ei].second;
}
vector<Arc> arcs;
vector<int> offsets;
};
class StronglyConnectedComponents {
public:
//typedef vector<vector<int>> Graph;
typedef StaticGraph Graph;
int run(const Graph &graph) {
int n = (int)graph.size();
stack.resize(n);
S.resize(n);
B.resize(n);
I.assign(n, 0);
int sp = 0, topS = 0, topB = 0, c = n;
for (int start = 0; start < n; ++start) if (I[start] == 0) {
stack[sp++] = make_pair(start, 0);
for (; sp != 0; ) {
int u, ei;
tie(u, ei) = stack[--sp];
if (ei == 0) {
S[topS++] = u;
B[topB++] = I[u] = topS;
}
if (ei != graph[u].size()) {
stack[sp++] = make_pair(u, ei + 1);
int v = graph[u][ei];
if (I[v] == 0) {
stack[sp++] = make_pair(v, 0);
}
else {
while (I[v] < B[topB - 1])
--topB;
}
}
else if (I[u] == B[topB - 1]) {
--topB, ++c;
while (I[u] <= topS)
I[S[--topS]] = c;
}
}
}
for (int u = 0; u < n; ++u)
I[u] -= n + 1;
return c - n;
}
int getColor(int u) const {
return I[u];
}
private:
vector<pair<int, int>> stack;
vector<int> S, B, I;
};
class TwoSatisfiability {
public:
void init(int variables) {
variableID.assign(variables, -1);
}
bool run(const vector<pair<int, int>> &clauses) {
currentVariables.clear();
edges.clear();
for (const auto &clause : clauses) {
int u = getVertex(clause.first);
int v = getVertex(clause.second);
edges.emplace_back(u ^ 1, v);
edges.emplace_back(v ^ 1, u);
}
int n = (int)currentVariables.size();
for (int var : currentVariables)
variableID[var] = -1;
graph.init(n * 2, edges);
scc.run(graph);
bool satisfiable = true;
for (int i = 0; i < n; ++i)
satisfiable &= scc.getColor(i * 2) != scc.getColor(i * 2 + 1);
return satisfiable;
}
void getAssignment(vector<bool> &res) {
int n = graph.size();
makeCondensation();
int S = condensation.size();
vector<int> deg(S);
rep(i, S) for (int j : condensation[i])
deg[j] ++;
vector<int> que(S, -1);
int qt = 0;
rep(i, S) if (deg[i] == 0)
que[qt++] = i;
for (int qh = 0; qh < qt; ++qh) {
int i = que[qh];
for (int j : condensation[i])
if (--deg[j] == 0)
que[qt++] = j;
}
vector<int> index(S, -1);
rep(i, S)
index[que[i]] = i;
rep(i, (int)currentVariables.size()) {
int ix0 = index[scc.getColor(i * 2 + 0)];
int ix1 = index[scc.getColor(i * 2 + 1)];
res[currentVariables[i]] = ix0 < ix1;
}
}
private:
void makeCondensation() {
int n = graph.size();
vector<pair<int, int>> edges;
rep(i, n) for (int j : graph[i]) if (scc.getColor(i) != scc.getColor(j))
edges.emplace_back(scc.getColor(i), scc.getColor(j));
int S = 0;
rep(i, n)
amax(S, scc.getColor(i) + 1);
condensation.init(S, edges);
}
int getVertex(int lit) {
int &id = variableID[lit >> 1];
if (id == -1) {
id = (int)currentVariables.size();
currentVariables.push_back(lit >> 1);
}
return id << 1 | (lit & 1);
}
vector<int> variableID;
vector<int> currentVariables;
vector<pair<int, int>> edges;
StronglyConnectedComponents::Graph graph;
StronglyConnectedComponents scc;
StronglyConnectedComponents::Graph condensation;
int sccS;
};
int main() {
TwoSatisfiability ts;
int N;
while (~scanf("%d", &N)) {
vector<string> Us(N);
rep(i, N) {
char U[4];
scanf("%s", U);
Us[i] = U;
}
if (N > 52) {
puts("Impossible");
continue;
}
vector<pair<int, int>> clauses;
auto addClause = [&](int i, int bi, int j, int bj) {
clauses.emplace_back(i * 2 + (1 - bi), j * 2 + (1 - bj));
};
rep(i, N) reu(j, i + 1, N) {
if (i < j) {
if (Us[i][0] == Us[j][0] || (Us[i][1] == Us[j][1] && Us[i][2] == Us[j][2]))
addClause(i, 0, j, 0);
if (Us[i][2] == Us[j][2] || (Us[i][0] == Us[j][0] && Us[i][1] == Us[j][1]))
addClause(i, 1, j, 1);
}
if (Us[i][0] == Us[j][2] || (Us[i][1] == Us[j][0] && Us[i][2] == Us[j][1]))
addClause(i, 0, j, 1);
if (Us[i][2] == Us[j][0] || (Us[i][0] == Us[j][1] && Us[i][1] == Us[j][2]))
addClause(i, 1, j, 0);
}
TwoSatisfiability twoSat;
twoSat.init(N);
bool ok = twoSat.run(clauses);
if (!ok) {
puts("Impossible");
}
else {
vector<bool> ans(N);
twoSat.getAssignment(ans);
rep(i, N) {
if (!ans[i])
printf("%c %c%c\n", Us[i][0], Us[i][1], Us[i][2]);
else
printf("%c%c %c\n", Us[i][0], Us[i][1], Us[i][2]);
}
}
}
return 0;
}