結果

問題 No.2168 双頭ヒドラゲーム
ユーザー SSRSSSRS
提出日時 2022-12-20 01:47:59
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,615 bytes
コンパイル時間 2,829 ms
コンパイル使用メモリ 200,368 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-18 01:43:01
合計ジャッジ時間 3,754 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
string advance(string &S, int &p){
  int cnt = 0;
  string ans;
  while (true){
    ans += S[p];
    if (S[p] == '('){
      cnt++;
    }
    if (S[p] == ')'){
      cnt--;
    }
    p++;
    if (cnt == 0 && S[p] != '('){
      break;
    }
  }
  return ans;
}
tuple<string, string, string> parse(string S){
  int p = 1;
  string s1;
  if (S[p] == '('){
    s1 = advance(S, p);
  }
  p++;
  string s2;
  if (S[p] == '('){
    s2 = advance(S, p);
  }
  p++;
  string s3 = S.substr(p);
  return make_tuple(s1, s2, s3);
}
map<pair<string, string>, int> mp;
int comp(string S, string T){
  if (S == "" && T == ""){
    return 0;
  }
  if (S == ""){
    return -1;
  }
  if (T == ""){
    return 1;
  }
  if (mp.count(make_pair(S, T))){
    return mp[make_pair(S, T)];
  }
  string SS = S, TT = T;
  vector<string> s;
  while (true){
    string S1, S2, S3;
    tie(S1, S2, S3) = parse(S);
    s.push_back("(" + S1 + "|" + S2 + ")");
    if (S3 == ""){
      break;
    }
    S = S3;
  }
  vector<string> t;
  while (true){
    string T1, T2, T3;
    tie(T1, T2, T3) = parse(T);
    t.push_back("(" + T1 + "|" + T2 + ")");
    if (T3 == ""){
      break;
    }
    T = T3;
  }
  int N = s.size();
  int M = t.size();
  vector<string> s2;
  s2.push_back(s[0]);
  for (int i = 1; i < N; i++){
    while (!s2.empty()){
      if (comp(s2.back(), s[i]) == -1){
        s2.pop_back();
      } else {
        break;
      }
    }
    s2.push_back(s[i]);
  }
  vector<string> t2;
  t2.push_back(t[0]);
  for (int i = 1; i < M; i++){
    while (!t2.empty()){
      if (comp(t2.back(), t[i]) == -1){
        t2.pop_back();
      } else {
        break;
      }
    }
    t2.push_back(t[i]);
  }
  N = s2.size();
  M = t2.size();
  int ans;
  if (N == 1 && M == 1){
    string S1 = get<0>(parse(s2[0]));
    string S2 = get<1>(parse(s2[0]));
    string T1 = get<0>(parse(t2[0]));
    string T2 = get<1>(parse(t2[0]));
    int p = comp(S1, T1);
    if (p == -1){
      ans = comp(S2, t2[0]);
    } else if (p == 1){
      ans = comp(s2[0], T2);
    } else {
      ans = comp(S2, T2);
    }
  } else {
    s2.push_back("");
    t2.push_back("");
    int p = 0;
    while (true){
      int r = comp(s2[p], t2[p]);
      if (r != 0){
        ans = r;
        break;
      }
      if (s2[p] == "" && t2[p] == ""){
        ans = 0;
        break;
      }
      p++;
    }
  }
  mp[make_pair(SS, TT)] = ans;
  return ans;
}
int main(){
  string T1;
  cin >> T1;
  string T2;
  cin >> T2;
  int ans = comp(T1, T2);
  if (ans == 1){
    cout << 0 << endl;
  } else {
    cout << 1 << endl;
  }
}
0