結果

問題 No.3134 二分探索木
ユーザー tobbie
提出日時 2025-05-29 18:17:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,442 bytes
コンパイル時間 2,105 ms
コンパイル使用メモリ 198,560 KB
実行使用メモリ 14,500 KB
最終ジャッジ日時 2025-05-29 18:17:30
合計ジャッジ時間 7,583 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 8 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; i++)

struct Node {
  int value;
  Node *left;
  Node *right;
};

int main() {
  int n;
  cin >> n;
  vector<int> a(n), ainv(n+1);
  rep(i, n) {
    cin >> a[i];
    ainv[a[i]] = i;
  }
  struct Node *tree = (struct Node*)malloc(sizeof(struct Node));
  tree->left = NULL;
  tree->right = NULL;
  tree->value = a[0];
  rep(i, n-1) {
    auto insert = [&](auto insert, struct Node *node, int x) {
      if (node == NULL) {
	struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->value = x;
	newNode->left = NULL;
	newNode->right = NULL;
	return newNode;
      }
      if (x < node->value)
	node->left = insert(insert, node->left, x);
      else
	node->right = insert(insert, node->right, x);
      return node;
    };
    tree = insert(insert, tree, a[i+1]);
  }
  vector<int> b(n), c(n);
  auto printNode = [&](auto printNode, struct Node *node, int d) {
    if (node == NULL)
      return 0;
    int r = 0;
    r += printNode(printNode, node->right, d+1);
    b[ainv[node->value]] = d;
    r += printNode(printNode, node->left, d+1);
    c[ainv[node->value]] = r;
    return r + 1;
  };
  printNode(printNode, tree, 0);
  rep(i, n) {
    cout << b[i];
    if (i < n-1) cout << " ";
    else         cout << endl;
  }
  rep(i, n) {
    cout << c[i];
    if (i < n-1) cout << " ";
    else         cout << endl;
  }
  return 0;
}
0