結果

問題 No.759 悪くない忘年会にしような！
ユーザー t33ft33f
提出日時 2018-12-10 19:52:14
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 602 ms / 2,000 ms
コード長 2,521 bytes
コンパイル時間 500 ms
コンパイル使用メモリ 66,112 KB
実行使用メモリ 162,288 KB
最終ジャッジ日時 2023-10-14 22:16:28
合計ジャッジ時間 10,856 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,352 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 2 ms
4,352 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 1 ms
4,352 KB
testcase_07 AC 1 ms
4,348 KB
testcase_08 AC 1 ms
4,348 KB
testcase_09 AC 2 ms
4,352 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 1 ms
4,348 KB
testcase_12 AC 1 ms
4,352 KB
testcase_13 AC 2 ms
4,348 KB
testcase_14 AC 2 ms
4,352 KB
testcase_15 AC 1 ms
4,348 KB
testcase_16 AC 1 ms
4,348 KB
testcase_17 AC 1 ms
4,352 KB
testcase_18 AC 2 ms
4,352 KB
testcase_19 AC 1 ms
4,348 KB
testcase_20 AC 1 ms
4,352 KB
testcase_21 AC 1 ms
4,352 KB
testcase_22 AC 1 ms
4,352 KB
testcase_23 AC 1 ms
4,348 KB
testcase_24 AC 2 ms
4,348 KB
testcase_25 AC 2 ms
4,352 KB
testcase_26 AC 2 ms
4,352 KB
testcase_27 AC 1 ms
4,348 KB
testcase_28 AC 1 ms
4,348 KB
testcase_29 AC 1 ms
4,352 KB
testcase_30 AC 2 ms
4,352 KB
testcase_31 AC 2 ms
4,348 KB
testcase_32 AC 2 ms
4,352 KB
testcase_33 AC 29 ms
18,268 KB
testcase_34 AC 7 ms
6,020 KB
testcase_35 AC 17 ms
11,448 KB
testcase_36 AC 29 ms
17,808 KB
testcase_37 AC 8 ms
6,816 KB
testcase_38 AC 31 ms
19,656 KB
testcase_39 AC 8 ms
7,184 KB
testcase_40 AC 22 ms
15,336 KB
testcase_41 AC 26 ms
17,148 KB
testcase_42 AC 33 ms
20,032 KB
testcase_43 AC 35 ms
21,340 KB
testcase_44 AC 397 ms
162,040 KB
testcase_45 AC 376 ms
162,000 KB
testcase_46 AC 352 ms
162,076 KB
testcase_47 AC 355 ms
162,176 KB
testcase_48 AC 364 ms
162,040 KB
testcase_49 AC 37 ms
21,416 KB
testcase_50 AC 36 ms
21,312 KB
testcase_51 AC 36 ms
21,400 KB
testcase_52 AC 36 ms
21,520 KB
testcase_53 AC 361 ms
162,060 KB
testcase_54 AC 357 ms
162,204 KB
testcase_55 AC 353 ms
162,128 KB
testcase_56 AC 357 ms
162,224 KB
testcase_57 AC 373 ms
162,172 KB
testcase_58 AC 364 ms
162,036 KB
testcase_59 AC 366 ms
162,124 KB
testcase_60 AC 361 ms
162,024 KB
testcase_61 AC 362 ms
162,148 KB
testcase_62 AC 357 ms
162,288 KB
testcase_63 AC 507 ms
36,568 KB
testcase_64 AC 602 ms
43,280 KB
testcase_65 AC 169 ms
43,208 KB
testcase_66 AC 554 ms
43,112 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <iostream>
using namespace std;

struct tree {
    int bot[3], top[3];
    int count, dim;
    tree *left, *right;
    tree(int bx, int by, int bz, int tx, int ty, int tz) {
        bot[0] = bx; bot[1] = by; bot[2] = bz;
        top[0] = tx; top[1] = ty; top[2] = tz;
        count = 0; dim = 0;
        left = NULL; right = NULL;
    };
    tree(int b[3], int t[3], int d) {
        for (int i = 0; i < 3; i++) bot[i] = b[i], top[i] = t[i];
        count = 0; dim = d;
        left = NULL; right = NULL;
    };
};
// bot[i] <= p[i] && p[i] <= top[i] for i = 0, 1, 2
// left: [bot[i], top[i]] and [bot[dim], (bot[dim] + top[dim])/2]
// right: ... and [(bot[dim] + top[dim])/2 + 1, top[dim]]

bool compat(int p[3], int q[3]) {
    return p[0] <= q[0] && p[1] <= q[1] && p[2] <= q[2] &&
            (p[0] < q[0] || p[1] < q[1] || p[2] < q[2]);
}

bool search(int p[3], tree &t) {
    if (t.count == 0) return false;
    if (compat(p, t.bot)) return true;
    if (!compat(p, t.top)) return false;
    return (t.right != NULL && search(p, *t.right)) ||
           (t.left != NULL && search(p, *t.left));
}

void add(int p[3], tree &t) {
    if (t.top[0] == t.bot[0] && t.top[1] == t.bot[1] && t.top[2] == t.bot[2]) {
        t.count = 1;
    } else {
        int m = (t.top[t.dim] + t.bot[t.dim]) / 2;
        if (p[t.dim] <= m) {    // left
            if (t.left == NULL) {
                int mid[3];
                for (int i = 0; i < 3; i++)
                    if (i == t.dim) mid[i] = m;
                    else mid[i] = t.top[i];
                t.left = (tree *)malloc(sizeof(tree));
                *t.left = tree(t.bot, mid, t.dim == 2 ? 0 : t.dim + 1);
            }
            add(p, *t.left);
        } else {                // right
            if (t.right == NULL) {
                int mid[3];
                for (int i = 0; i < 3; i++)
                    if (i == t.dim) mid[i] = m + 1;
                    else mid[i] = t.bot[i];
                t.right = (tree *)malloc(sizeof(tree));
                *t.right = tree(mid, t.top, t.dim == 2 ? 0 : t.dim + 1);
            }
            add(p, *t.right);
        }
        t.count++;
    }
}

int main() {
    int n; cin >> n;
    tree t(0, 0, 0, 10000, 10000, 10000);
    int a[100100][3];
    for (int i = 0; i < n; i++) {
        int x, y, z;
        scanf(" %d %d %d", &a[i][0], &a[i][1], &a[i][2]);
        add(a[i], t);
    }
    for (int i = 1; i <= n; i++) {
        if (!search(a[i-1], t)) cout << i << endl;
    }
}
0