結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 1 ms
5,376 KB
testcase_33 AC 31 ms
18,304 KB
testcase_34 AC 6 ms
6,144 KB
testcase_35 AC 18 ms
11,648 KB
testcase_36 AC 31 ms
17,920 KB
testcase_37 AC 8 ms
6,912 KB
testcase_38 AC 34 ms
19,840 KB
testcase_39 AC 9 ms
6,912 KB
testcase_40 AC 25 ms
15,360 KB
testcase_41 AC 29 ms
17,152 KB
testcase_42 AC 35 ms
20,096 KB
testcase_43 AC 37 ms
21,504 KB
testcase_44 AC 362 ms
162,176 KB
testcase_45 AC 350 ms
162,176 KB
testcase_46 AC 359 ms
162,176 KB
testcase_47 AC 353 ms
162,432 KB
testcase_48 AC 362 ms
162,176 KB
testcase_49 AC 37 ms
21,376 KB
testcase_50 AC 37 ms
21,376 KB
testcase_51 AC 37 ms
21,504 KB
testcase_52 AC 37 ms
21,504 KB
testcase_53 AC 353 ms
162,304 KB
testcase_54 AC 359 ms
162,176 KB
testcase_55 AC 354 ms
162,176 KB
testcase_56 AC 359 ms
162,176 KB
testcase_57 AC 352 ms
162,176 KB
testcase_58 AC 360 ms
162,048 KB
testcase_59 AC 358 ms
162,176 KB
testcase_60 AC 359 ms
162,176 KB
testcase_61 AC 359 ms
162,176 KB
testcase_62 AC 361 ms
162,176 KB
testcase_63 AC 498 ms
36,608 KB
testcase_64 AC 524 ms
43,136 KB
testcase_65 AC 180 ms
43,392 KB
testcase_66 AC 779 ms
43,520 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