結果
| 問題 | No.470 Inverse S+T Problem |
| ユーザー |
 Drafear
|
| 提出日時 | 2018-11-03 14:36:59 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,138 bytes |
| コンパイル時間 | 1,881 ms |
| コンパイル使用メモリ | 179,360 KB |
| 実行使用メモリ | 353,664 KB |
| 最終ジャッジ日時 | 2023-08-24 01:33:45 |
| 合計ジャッジ時間 | 8,855 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | AC | 2 ms
4,380 KB |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | AC | 1,713 ms
352,940 KB |
| testcase_07 | AC | 1,714 ms
353,104 KB |
| testcase_08 | AC | 1,775 ms
353,664 KB |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | AC | 2 ms
4,380 KB |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | AC | 2 ms
4,380 KB |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | AC | 2 ms
4,376 KB |
| testcase_25 | AC | 2 ms
4,376 KB |
| testcase_26 | AC | 2 ms
4,376 KB |
| testcase_27 | AC | 2 ms
4,376 KB |
| testcase_28 | AC | 182 ms
48,256 KB |
| testcase_29 | AC | 14 ms
8,060 KB |
| testcase_30 | AC | 85 ms
25,484 KB |
コンパイルメッセージ
main.cpp:22:17: warning: overflow in conversion from ‘double’ to ‘ll’ {aka ‘int’} changes value from ‘1.0e+18’ to ‘2147483647’ [-Woverflow]
const ll linf = 1e18;
^~~~
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> P;
#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);
template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
each(x,vec) is >> x;
return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
rep(i,vec.size()) {
if (i) os << " ";
os << vec[i];
}
return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
rep(i,vec.size()) {
if (i) os << endl;
os << vec[i];
}
return os;
}
void scc_dfs(ll v, vector<bool>& used, vector<ll>& vs, const vector<vector<ll>>& G) {
used[v] = true;
each(to, G[v]) {
if (!used[to]) scc_dfs(to, used, vs, G);
}
vs.pb(v);
}
void scc_rdfs(ll v, ll k, vector<bool>& used, vector<ll>& cmp, const vector<vector<ll>>& rG) {
used[v] = true;
cmp[v] = k;
each(to, rG[v]) {
if (!used[to]) scc_rdfs(to, k, used, cmp, rG);
}
}
// cmpが返る
// 同じcmpは強連結成分
// cmp[i] < cmp[j] なら j から i に行けない
vector<ll> scc(const vector<vector<ll>>& G) {
const ll n = G.size();
vector<bool> used(n, false);
vector<ll> vs;
rep(i, n) {
if (!used[i]) scc_dfs(i, used, vs, G);
}
used.assign(n, false);
vector<vector<ll>> rG(n);
rep(i, n) {
each(to, G[i]) {
rG[to].pb(i);
}
}
vector<ll> res(n);
ll k = 0;
rrep(i, vs.size()) {
if (!used[vs[i]]) scc_rdfs(vs[i], k++, used, res, rG);
}
return res;
}
vector<vector<ll>> get_scc_graph(const vector<ll>& cmp, const vector<vector<ll>>& G) {
vector<vector<ll>> res(*max_element(all(cmp))+1);
rep(i, G.size()) {
each(to, G[i]) {
if (cmp[i] != cmp[to]) {
res[cmp[i]].pb(cmp[to]);
}
}
}
rep(i, res.size()) {
sort(all(res[i]));
res[i].erase(unique(all(res[i])), res[i].end());
}
return res;
}
class Sat {
ll n;
vector<vector<ll>> G;
ll node_id(ll id, bool b) const {
return id * 2 + b;
}
public:
Sat(ll size) : n(size), G(size*2) {}
// (id1, b1) => (id2, b2)
void add(ll id1, bool b1, ll id2, bool b2) {
G[node_id(id1, b1)].pb(node_id(id2, b2));
G[node_id(id2, !b2)].pb(node_id(id1, !b1));
}
bool check() const {
vector<ll> cmp = scc(G);
rep(i, n) {
if (cmp[node_id(i, true)] == cmp[node_id(i, false)]) {
return false;
}
}
return true;
}
vector<bool> solve() const {
assert( check() );
vector<ll> cmp = scc(G);
vector<bool> used(n, false), res(n);
vector<P> v;
rep(i, 2*n) v.eb(cmp[i], i);
sort(all(v), greater<P>());
stack<ll> S;
each(p, v) {
ll i = p.second;
if (used[i/2]) continue;
used[i/2] = true;
S.push(i);
while ( !S.empty() ) {
ll v = S.top(); S.pop();
res[v/2] = v & 1;
each(to, G[v]) {
if (used[to/2]) continue;
used[to/2] = true;
S.push(to);
}
}
}
return res;
}
};
int main() {
// {
// Sat sat(3);
// sat.add(0, true, 1, false);
// sat.add(1, false, 1, true);
// sat.add(2, true, 0, true);
// cout << sat.solve() << endl;
// return 0;
// }
ios::sync_with_stdio(false);
cin.tie(0);
ll n; cin >> n;
vector<string> s(n); cin >> s;
Sat sat(9*n);
ll idx = n;
map<string, vector<pair<ll, bool>>> m;
rep(i, n) {
m[s[i].substr(0, 1)].eb(i, false);
m[s[i].substr(1, 2)].eb(i, false);
m[s[i].substr(0, 2)].eb(i, true);
m[s[i].substr(2, 1)].eb(i, true);
}
each(p, m) {
// left
rep(i, 1, p.second.size()) {
sat.add(idx+i, true, idx+i-1, true);
}
rep(i, p.second.size()) {
bool b = p.second[i].second;
if (i > 0) sat.add(p.second[i].first, b, idx+i-1, true);
sat.add(idx+i, true, p.second[i].first, !b);
}
idx += p.second.size();
// right
rep(i, 1, p.second.size()) {
sat.add(idx+i-1, true, idx+i, true);
}
rep(i, p.second.size()) {
bool b = p.second[i].second;
if (i+1 < p.second.size()) sat.add(p.second[i].first, b, idx+i+1, true);
sat.add(idx+i, true, p.second[i].first, !b);
}
idx += p.second.size();
}
if (!sat.check()) {
cout << "Impossible" << endl;
}
else {
// vector<bool> ans = sat.solve();
// rep(i, n) {
// if (!ans[i]) {
// cout << s[i].substr(0, 1) << " " << s[i].substr(1, 2) << '\n';
// }
// else {
// cout << s[i].substr(0, 2) << " " << s[i].substr(2, 1) << '\n';
// }
// }
// cout << flush;
}
}