結果
| 問題 | No.470 Inverse S+T Problem |
| ユーザー |
 Coki628
|
| 提出日時 | 2020-12-16 17:12:56 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,916 bytes |
| コンパイル時間 | 2,891 ms |
| コンパイル使用メモリ | 235,208 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-06-01 23:06:05 |
| 合計ジャッジ時間 | 4,189 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | AC | 2 ms
6,812 KB |
| testcase_02 | AC | 2 ms
6,816 KB |
| testcase_03 | AC | 2 ms
6,944 KB |
| testcase_04 | AC | 2 ms
6,940 KB |
| testcase_05 | AC | 2 ms
6,944 KB |
| testcase_06 | AC | 2 ms
6,940 KB |
| testcase_07 | AC | 2 ms
6,940 KB |
| testcase_08 | AC | 2 ms
6,940 KB |
| testcase_09 | AC | 2 ms
6,940 KB |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | AC | 2 ms
6,940 KB |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | AC | 2 ms
6,940 KB |
| testcase_16 | AC | 2 ms
6,940 KB |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | AC | 2 ms
6,944 KB |
| testcase_20 | AC | 2 ms
6,940 KB |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | AC | 2 ms
6,944 KB |
| testcase_25 | AC | 2 ms
6,944 KB |
| testcase_26 | AC | 2 ms
6,944 KB |
| testcase_27 | AC | 2 ms
6,940 KB |
| testcase_28 | AC | 2 ms
6,944 KB |
| testcase_29 | AC | 2 ms
6,940 KB |
| testcase_30 | AC | 2 ms
6,944 KB |
ソースコード
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using vvl = vector<vector<ll>>;
using vvi = vector<vector<int>>;
using vvpll = vector<vector<pll>>;
#define rep(i, a, b) for (ll i=(a); i<(b); i++)
#define rrep(i, a, b) for (ll i=(a); i>(b); i--)
#define pb push_back
#define tostr to_string
#define ALL(A) A.begin(), A.end()
constexpr ll INF = LONG_LONG_MAX;
constexpr ll MOD = 1000000007;
template<typename T> vector<vector<T>> list2d(int N, int M, T init) { vector<vector<T>> res(N, vector<T>(M, init)); return res; }
template<typename T> vector<vector<vector<T>>> list3d(int N, int M, int L, T init) { vector<vector<vector<T>>> res(N, vector<vector<T>>(M, vector<T>(L, init))); return res; }
void print(ld out) { cout << fixed << setprecision(15) << out << '\n'; }
void print(double out) { cout << fixed << setprecision(15) << out << '\n'; }
template<typename T> void print(T out) { cout << out << '\n'; }
template<typename T1, typename T2> void print(pair<T1, T2> out) { cout << out.first << ' ' << out.second << '\n'; }
template<typename T> void print(vector<T> A) { rep(i, 0, A.size()) { cout << A[i]; cout << (i == A.size()-1 ? '\n' : ' '); } }
template<typename T> void print(set<T> S) { vector<T> A(S.begin(), S.end()); print(A); }
void Yes() { print("Yes"); }
void No() { print("No"); }
void YES() { print("YES"); }
void NO() { print("NO"); }
ll floor(ll a, ll b) { if (a < 0) { return (a-b+1) / b; } else { return a / b; } }
ll ceil(ll a, ll b) { if (a >= 0) { return (a+b-1) / b; } else { return a / b; } }
pll divmod(ll a, ll b) { ll d = a / b; ll m = a % b; return {d, m}; }
template<typename T> bool chmax(T &x, T y) { return (y > x) ? x = y, true : false; }
template<typename T> bool chmin(T &x, T y) { return (y < x) ? x = y, true : false; }
template<typename T> T sum(vector<T> A) { T res = 0; for (T a: A) res += a; return res; }
template<typename T> T max(vector<T> A) { return *max_element(ALL(A)); }
template<typename T> T min(vector<T> A) { return *min_element(ALL(A)); }
ll toint(string s) { ll res = 0; for (char c : s) { res *= 10; res += (c - '0'); } return res; }
int toint(char num) { return num - '0'; }
char tochar(int num) { return '0' + num; }
int ord(char c) { return (int)c; }
char chr(int a) { return (char)a; }
ll pow(int x, ll n) { ll res = 1; rep(_, 0, n) res *= x; return res; }
ll pow(ll x, ll n, int mod) { ll res = 1; while (n > 0) { if (n & 1) { res = (res * x) % mod; } x = (x * x) % mod; n >>= 1; } return res; }
int popcount(ll S) { return __builtin_popcountll(S); }
ll gcd(ll a, ll b) { return __gcd(a, b); }
#ifndef ATCODER_INTERNAL_SCC_HPP
#define ATCODER_INTERNAL_SCC_HPP 1
#include <algorithm>
#include <utility>
#include <vector>
namespace atcoder {
namespace internal {
template <class E> struct csr {
std::vector<int> start;
std::vector<E> elist;
csr(int n, const std::vector<std::pair<int, E>>& edges)
: start(n + 1), elist(edges.size()) {
for (auto e : edges) {
start[e.first + 1]++;
}
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
auto counter = start;
for (auto e : edges) {
elist[counter[e.first]++] = e.second;
}
}
};
// Reference:
// R. Tarjan,
// Depth-First Search and Linear Graph Algorithms
struct scc_graph {
public:
scc_graph(int n) : _n(n) {}
int num_vertices() { return _n; }
void add_edge(int from, int to) { edges.push_back({from, {to}}); }
// @return pair of (# of scc, scc id)
std::pair<int, std::vector<int>> scc_ids() {
auto g = csr<edge>(_n, edges);
int now_ord = 0, group_num = 0;
std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
visited.reserve(_n);
auto dfs = [&](auto self, int v) -> void {
low[v] = ord[v] = now_ord++;
visited.push_back(v);
for (int i = g.start[v]; i < g.start[v + 1]; i++) {
auto to = g.elist[i].to;
if (ord[to] == -1) {
self(self, to);
low[v] = std::min(low[v], low[to]);
} else {
low[v] = std::min(low[v], ord[to]);
}
}
if (low[v] == ord[v]) {
while (true) {
int u = visited.back();
visited.pop_back();
ord[u] = _n;
ids[u] = group_num;
if (u == v) break;
}
group_num++;
}
};
for (int i = 0; i < _n; i++) {
if (ord[i] == -1) dfs(dfs, i);
}
for (auto& x : ids) {
x = group_num - 1 - x;
}
return {group_num, ids};
}
std::vector<std::vector<int>> scc() {
auto ids = scc_ids();
int group_num = ids.first;
std::vector<int> counts(group_num);
for (auto x : ids.second) counts[x]++;
std::vector<std::vector<int>> groups(ids.first);
for (int i = 0; i < group_num; i++) {
groups[i].reserve(counts[i]);
}
for (int i = 0; i < _n; i++) {
groups[ids.second[i]].push_back(i);
}
return groups;
}
private:
int _n;
struct edge {
int to;
};
std::vector<std::pair<int, edge>> edges;
};
} // namespace internal
} // namespace atcoder
#endif // ATCODER_INTERNAL_SCC_HPP
#ifndef ATCODER_TWOSAT_HPP
#define ATCODER_TWOSAT_HPP 1
#include <cassert>
#include <vector>
namespace atcoder {
// Reference:
// B. Aspvall, M. Plass, and R. Tarjan,
// A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean
// Formulas
struct two_sat {
public:
two_sat() : _n(0), scc(0) {}
two_sat(int n) : _n(n), _answer(n), scc(2 * n) {}
void add_clause(int i, bool f, int j, bool g) {
assert(0 <= i && i < _n);
assert(0 <= j && j < _n);
scc.add_edge(2 * i + (f ? 0 : 1), 2 * j + (g ? 1 : 0));
scc.add_edge(2 * j + (g ? 0 : 1), 2 * i + (f ? 1 : 0));
}
bool satisfiable() {
auto id = scc.scc_ids().second;
for (int i = 0; i < _n; i++) {
if (id[2 * i] == id[2 * i + 1]) return false;
_answer[i] = id[2 * i] < id[2 * i + 1];
}
return true;
}
std::vector<bool> answer() { return _answer; }
private:
int _n;
std::vector<bool> _answer;
internal::scc_graph scc;
};
} // namespace atcoder
#endif // ATCODER_TWOSAT_HPP
using namespace atcoder;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
map<string, vector<pair<ll, bool>>> cond;
ll N;
cin >> N;
if (N > 26) {
print("Impossible");
return 0;
}
vector<string> A(N);
rep(i, 0, N) {
string s;
cin >> s;
cond[s.substr(0, 2)].pb({i, 1});
cond[s.substr(2)].pb({i, 1});
cond[s.substr(0, 1)].pb({i, 0});
cond[s.substr(1)].pb({i, 0});
A[i] = s;
}
// ts[i] := i番目の文字列を前2,後ろ1で切る
two_sat ts(N);
for (auto& [s, li] : cond) {
ll m = li.size();
rep(i, 0, m) {
auto [idx1, flag1] = li[i];
rep(j, i+1, m) {
auto [idx2, flag2] = li[j];
ts.add_clause(idx1, 1-flag1, idx2, 1-flag2);
}
}
}
if (ts.satisfiable()) {
auto ans = ts.answer();
rep(i, 0, N) {
if (ans[i]) {
cout << A[i].substr(0, 2) << ' ' << A[i].substr(2) << '\n';
} else {
cout << A[i].substr(0, 1) << ' ' << A[i].substr(1) << '\n';
}
}
} else {
print("Impossible");
}
return 0;
}