結果
問題 | No.2168 双頭ヒドラゲーム |
ユーザー | 👑 Nachia |
提出日時 | 2022-12-20 15:21:25 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,652 bytes |
コンパイル時間 | 1,020 ms |
コンパイル使用メモリ | 88,460 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-18 01:50:54 |
合計ジャッジ時間 | 1,923 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 2 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | AC | 2 ms
6,816 KB |
testcase_19 | AC | 2 ms
6,820 KB |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 2 ms
6,816 KB |
testcase_23 | AC | 2 ms
6,816 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;}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);}sort(L.rbegin(), L.rend(), ltp);sort(R.rbegin(), R.rend(), ltp);return lexicographical_compare(L.begin(), L.end(), R.begin(), R.end(), ltp);}int main(){string chars = ")|(";string T0, T1; cin >> T0 >> T1;int p0 = 0, p1 = 0;auto t0 = construct(T0, p0);auto t1 = construct(T1, p1);if(lt(t0, t1)) cout << "1\n"; else cout << "0\n";return 0;}