結果
問題 | No.2168 双頭ヒドラゲーム |
ユーザー | 👑 Nachia |
提出日時 | 2022-12-20 23:10:23 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,862 bytes |
コンパイル時間 | 886 ms |
コンパイル使用メモリ | 85,988 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-04-29 03:00:22 |
合計ジャッジ時間 | 1,699 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | WA | - |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | WA | - |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | WA | - |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 2 ms
5,376 KB |
ソースコード
// (X|Y)Z = φ_X (Y) + Z #include <iostream> #include <string> #include <vector> #include <algorithm> #include <utility> #include <array> #include <atcoder/modint> using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; struct Node { Node* p[3] = {}; }; Node* construct(string s, int& p){ if(p == (int)s.size()) return nullptr; if(s[p] != '(') return nullptr; Node* res = new Node(); p++; res->p[0] = construct(s, p); p++; res->p[1] = construct(s, p); p++; res->p[2] = construct(s, p); return res; } string reverse_construct(Node* p){ if(!p) return ""; return "(" + reverse_construct(p->p[0]) + "|" + reverse_construct(p->p[1]) + ")" + reverse_construct(p->p[2]); } bool lt(Node *l, Node *r){ auto ltp = [](pair<Node*, Node*> l, pair<Node*, Node*> r) -> bool { if(lt(l.first, r.first)) return true; if(lt(r.first, l.first)) return false; return lt(l.second, r.second); }; vector<pair<Node*, Node*>> L, R; rep(x,2){ while(l){ auto nx = make_pair(l->p[0], l->p[1]); //while(L.size() && ltp(L.back(), nx)) L.pop_back(); L.push_back(nx); l = l->p[2]; } swap(l,r); swap(L,R); } return lexicographical_compare(L.begin(), L.end(), R.begin(), R.end(), ltp); } int main(){ string chars = ")|("; string T0, T1; getline(cin, T0); getline(cin, T1); int p0 = 0, p1 = 0; auto t0 = construct(T0, p0); auto t1 = construct(T1, p1); assert(reverse_construct(t0) == T0); assert(reverse_construct(t1) == T1); if(lt(t1, t0)) cout << "0\n"; else cout << "1\n"; return 0; }