結果

問題 No.2168 双頭ヒドラゲーム
コンテスト
ユーザー chro_96
提出日時 2022-12-20 23:25:14
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 4,491 bytes
コンパイル時間 471 ms
コンパイル使用メモリ 30,592 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-18 02:10:03
合計ジャッジ時間 1,822 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 23 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

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

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

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

tree tree_pool[1000000] = {};
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 = 0;
  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;
    l1 = tmp_list;
    tmp_tree = tmp_tree->t[2];
  }
  
  /*
  while (l1 != NULL && l2 != NULL) {
    if (l1->t->t[0] == NULL && l1->t->t[2] == NULL) {
    }
  }
  */
  
  return 0;
}

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);
  
  if (res > 0) {
    printf("0\n");
  } else {
    printf("1\n");
  }
  
  tree2str(t0_tree, buf);
  printf("%s\n", buf);
  tree2str(t1_tree, buf);
  printf("%s\n", buf);
  
  return 0;
}
0