結果
問題 | No.2168 双頭ヒドラゲーム |
ユーザー |
![]() |
提出日時 | 2022-12-20 15:38:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,043 bytes |
コンパイル時間 | 2,748 ms |
コンパイル使用メモリ | 216,724 KB |
最終ジャッジ日時 | 2025-02-09 17:21:43 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 WA * 7 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<(b);++i) #define all(n) (n).begin(),(n).end() // カントールの標準形に直す struct tree{ vector<tree>v; tree(){ } tree operator+(const tree& b){ tree res; for(auto c:v){ if(!b.v.empty()&&c<b.v[0])break; res.v.emplace_back(c); } for(auto c:b.v){ res.v.emplace_back(c); } sort(res.v.begin(),res.v.end()); reverse(res.v.begin(),res.v.end()); return res; } tree mul_omega()const{ tree res=*this; tree one; one.v.emplace_back(tree()); for(auto& c:res.v){ c=move(c)+one; } return res; } void print(string s=""){ for(auto e:v){ cerr<<s+"-"<<endl; e.print(s+" "); } } bool operator==(const tree&b)const{ return v==b.v; } bool operator<(const tree&b)const{ return v<b.v; } }; // (a|b)=omega^(omega a)+omega b ? tree string_to_tree(string s){ if(s=="")return tree(); assert(s[0]=='('); int idx=1,idx2=1,val=0; tree ch[2]={}; bool right=0; while(1){ if(val==0&&s[idx2]=='|'){ right=1; idx=idx2+1; idx2=idx; continue; } if(s[idx2]=='(')val++; if(val==0&&s[idx2]==')'){ break; } if(s[idx2]==')')val--; if(val==0){ // cerr<<s.substr(idx,idx2-idx+1)<<endl; ch[right]=string_to_tree(s.substr(idx,idx2-idx+1))+move(ch[right]); idx=idx2+1; } idx2++; } auto rtree=ch[1].mul_omega(); auto ltree=tree(); ltree.v.emplace_back(ch[0].mul_omega()); return rtree+ltree; } int main(){ string s; string t; cin>>s>>t; s="(|"+s+")"; t="(|"+t+")"; auto ts=string_to_tree(s); auto tt=string_to_tree(t); // ts.print(); // tt.print(); cout<<(tt<ts?0:1)<<endl; }