#827339 (C) No.2168 双頭ヒドラゲーム

• 問題: No.2168 双頭ヒドラゲーム
• ユーザー: chro_96
• 提出日時: 2022-12-20 23:49:03
• 言語: C (gcc 13.3.0)
• 結果: WA
• 実行時間: -
• コード長: 5,941 bytes
• コンパイル時間: 316 ms
• コンパイル使用メモリ: 31,616 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-11-18 02:11:04
• 合計ジャッジ時間: 1,190 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
other	AC * 19 WA * 4 RE * 1

ソースコード

#include <stdio.h>

typedef struct tree {
  struct tree *t[3];
} tree;

typedef struct list {
  tree *t;
  struct list *n;
} list;

list list_pool[20000000] = {};
int list_used = 0;

tree tree_pool[20000000] = {};
int tree_used = 0;

tree *str2tree_rec (char *s, int *idx) {
  tree *ans = NULL;
  
  if (s[*idx] != '(') {
    return NULL;
  }
  
  ans = tree_pool+tree_used;
  tree_used++;
  
  *idx += 1;
  ans->t[0] = str2tree_rec(s, idx);
  *idx += 1;
  ans->t[1] = str2tree_rec(s, idx);
  *idx += 1;
  ans->t[2] = str2tree_rec(s, idx);
  
  return ans;
}

tree *str2tree (char *s) {
  int idx = 0;
  return str2tree_rec(s, &idx);
}

void tree2str_rec (tree *t, char *buf, int *idx) {
  if (t == NULL) {
    return;
  }
  
  buf[*idx] = '(';
  *idx += 1;
  tree2str_rec(t->t[0], buf, idx);
  buf[*idx] = '|';
  *idx += 1;
  tree2str_rec(t->t[1], buf, idx);
  buf[*idx] = ')';
  *idx += 1;
  tree2str_rec(t->t[2], buf, idx);
  buf[*idx] = '\0';
  
  return;
}

void tree2str (tree *t, char *buf) {
  int idx = 0;
  tree2str_rec(t, buf, &idx);
  return;
}

tree *copy_tree (tree *t) {
  tree *ans = NULL;
  
  if (t != NULL) {
    return NULL;
  }
  
  ans = tree_pool+tree_used;
  tree_used++;
  
  ans->t[0] = copy_tree(t->t[0]);
  ans->t[1] = copy_tree(t->t[1]);
  ans->t[2] = copy_tree(t->t[2]);
  
  return ans;
}

tree *get_zero_tree (tree *t) {
  tree *ans = NULL;
  
  if (t == NULL || (t->t[0] == NULL && t->t[1] == NULL && t->t[2] == NULL)) {
    return NULL;
  }
  
  ans = tree_pool+tree_used;
  tree_used++;
  
  if (t->t[2] != NULL) {
    ans->t[0] = copy_tree(t->t[0]);
    ans->t[1] = copy_tree(t->t[1]);
    ans->t[2] = get_zero_tree(t->t[2]);
    return ans;
  }
  
  if (t->t[0] == NULL) {
    ans->t[1] = get_zero_tree(t->t[1]);
    return ans;
  }
  
  if (t->t[1] == NULL) {
    ans->t[0] = get_zero_tree(t->t[0]);
    return ans;
  }
  
  if (t->t[1]->t[2] == NULL || t->t[1]->t[2]->t[0] != NULL || t->t[1]->t[2]->t[1] != NULL || t->t[1]->t[2]->t[2] != NULL) {
    ans->t[0] = copy_tree(t->t[0]);
    ans->t[1] = get_zero_tree(t->t[1]);
    return ans;
  }
  
  ans->t[0] = get_zero_tree(t->t[0]);
  ans->t[1] = tree_pool+tree_used;
  tree_used++;
  ans->t[1]->t[0] = copy_tree(t->t[0]);
  ans->t[1]->t[1] = get_zero_tree(t->t[1]);
  ans->t[1]->t[2] = tree_pool+tree_used;
  tree_used++;
  
  return ans;
}

void trans_single_head (tree *t) {
  if (t == NULL) {
    return;
  }
  
  if (t->t[0] == NULL || t->t[1] == NULL) {
    trans_single_head(t->t[0]);
    trans_single_head(t->t[1]);
    trans_single_head(t->t[2]);
    return;
  }
  
  if (t->t[1]->t[2] != NULL) {
    tree *t1 = t->t[1];
    tree *t2 = t->t[2];
    tree *cp = copy_tree(t->t[0]);
    tree *new_t2 = t1;
    tree *tmp = t;
    t->t[1] = NULL;
    while (cp != NULL) {
      tree *new = tree_pool+tree_used;
      tree_used++;
      new->t[0] = cp;
      new->t[2] = new_t2;
      new_t2 = new;
      cp = get_zero_tree(cp);
    }
    t->t[2] = new_t2;
    while (tmp->t[2] != NULL) {
      tmp = tmp->t[1];
    }
    tmp->t[2] = t2;
    trans_single_head(t->t[0]);
    trans_single_head(t->t[2]);
    return;
  }
  
  t->t[1]->t[2] = t->t[2];
  t->t[2] = t->t[1];
  t->t[1] = NULL;
  trans_single_head(t->t[0]);
  trans_single_head(t->t[2]);
  return;
}

int compare (tree *t1, tree *t2, int alt);

int compare_rec (tree *t1, tree *t2) {
  int res = 0;
  int tmp = 0;
  
  if (t2 == NULL) {
    return 1;
  }
  
  if (t2->t[0] != NULL && compare(t2->t[0], t1, 1) > 0) {
    return -1;
  }
  
  res = compare_rec(t1, t2->t[1]);
  if (res < 0) {
    return -1;
  }
  
  tmp = compare_rec(t1, t2->t[1]);
  if (tmp < 0) {
    return -1;
  }
  
  return 1;
}

int compare (tree *t1, tree *t2, int alt) {
  list *l1 = NULL;
  list *l2 = NULL;
  tree *tmp_tree = t1;
  int res = 0;
  
  while (tmp_tree != NULL) {
    list *tmp_list = list_pool+list_used;
    list_used++;
    tmp_list->t = tmp_tree;
    tmp_list->n = l1;
    l1 = tmp_list;
    tmp_tree = tmp_tree->t[2];
  }
  
  tmp_tree = t2;
  while (tmp_tree != NULL) {
    list *tmp_list = list_pool+list_used;
    list_used++;
    tmp_list->t = tmp_tree;
    tmp_list->n = l2;
    l2 = tmp_list;
    tmp_tree = tmp_tree->t[2];
  }
  
  while (l1 != NULL && l2 != NULL) {
    if (l1->t->t[0] == NULL && l1->t->t[1] == NULL) {
      if (l2->t->t[0] == NULL && l2->t->t[1] == NULL) {
        l2 = l2->n;
      } else {
        alt = 1;
      }
      l1 = l1->n;
    } else if (l2->t->t[0] == NULL && l2->t->t[1] == NULL) {
      alt = 0;
      l2 = l2->n;
    } else if (l1->t->t[0] != NULL && l2->t->t[0] != NULL) {
      res = compare(l1->t->t[0], l2->t->t[0], alt);
      if (res > 0) {
        l2 = l2->n;
        alt = 0;
      } else {
        l1 = l1->n;
        alt = 1;
      }
    } else if (l1->t->t[1] != NULL && l2->t->t[1] != NULL) {
      res = compare(l1->t->t[1], l2->t->t[1], alt);
      if (res > 0) {
        l2 = l2->n;
        alt = 0;
      } else {
        l1 = l1->n;
        alt = 1;
      }
    } else if (l1->t->t[0] != NULL) {
      res = compare_rec(l1->t->t[0], l2->t->t[1]);
      if (res > 0) {
        l2 = l2->n;
        alt = 0;
      } else {
        l1 = l1->n;
        alt = 1;
      }
    } else {
      res = compare_rec(l2->t->t[0], l1->t->t[1]);
      if (res > 0) {
        l1 = l1->n;
        alt = 1;
      } else {
        l2 = l2->n;
        alt = 1;
      }
    }
  }
  
  if (l2 != NULL || (l1 == NULL && l2 == NULL && alt <= 0)) {
    return 0;
  }
  
  return 1;
}

int main () {
  char t0[31] = "";
  char t1[31] = "";
  
  int res = 0;
  
  tree *t0_tree = NULL;
  tree *t1_tree = NULL;
  
  list *cnt[2] = {};
  
  char buf[1000001] = "";
  
  res = scanf("%s", t0);
  res = scanf("%s", t1);
  
  t0_tree = str2tree(t0);
  t1_tree = str2tree(t1);
  
  trans_single_head(t0_tree);
  trans_single_head(t1_tree);
  
  res = compare(t0_tree, t1_tree, 0);
  
  if (res > 0) {
    printf("0\n");
  } else {
    printf("1\n");
  }
  
  return 0;
}