結果

問題 No.759 悪くない忘年会にしような!
ユーザー t33ft33f
提出日時 2018-12-10 19:52:14
言語 C++14
(gcc 10.1.0 + boost 1.73.0)
結果
AC  
実行時間 582 ms / 2,000 ms
コード長 2,521 Byte
コンパイル時間 415 ms
使用メモリ 160,324 KB
最終ジャッジ日時 2020-07-03 07:25:15

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 2 ms
1,612 KB
testcase_01 AC 2 ms
1,608 KB
testcase_02 AC 2 ms
1,608 KB
testcase_03 AC 3 ms
1,612 KB
testcase_04 AC 2 ms
1,612 KB
testcase_05 AC 2 ms
1,604 KB
testcase_06 AC 2 ms
1,616 KB
testcase_07 AC 2 ms
1,604 KB
testcase_08 AC 2 ms
1,608 KB
testcase_09 AC 2 ms
1,612 KB
testcase_10 AC 2 ms
1,608 KB
testcase_11 AC 2 ms
1,616 KB
testcase_12 AC 2 ms
1,608 KB
testcase_13 AC 2 ms
1,604 KB
testcase_14 AC 2 ms
1,612 KB
testcase_15 AC 2 ms
1,608 KB
testcase_16 AC 2 ms
1,608 KB
testcase_17 AC 2 ms
1,604 KB
testcase_18 AC 2 ms
1,608 KB
testcase_19 AC 2 ms
1,608 KB
testcase_20 AC 2 ms
1,612 KB
testcase_21 AC 2 ms
1,608 KB
testcase_22 AC 2 ms
1,604 KB
testcase_23 AC 2 ms
1,608 KB
testcase_24 AC 2 ms
1,604 KB
testcase_25 AC 2 ms
1,616 KB
testcase_26 AC 2 ms
1,608 KB
testcase_27 AC 2 ms
1,604 KB
testcase_28 AC 2 ms
1,608 KB
testcase_29 AC 2 ms
1,608 KB
testcase_30 AC 3 ms
1,612 KB
testcase_31 AC 2 ms
1,608 KB
testcase_32 AC 2 ms
1,608 KB
testcase_33 AC 31 ms
16,356 KB
testcase_34 AC 7 ms
4,176 KB
testcase_35 AC 18 ms
9,580 KB
testcase_36 AC 32 ms
16,016 KB
testcase_37 AC 8 ms
4,892 KB
testcase_38 AC 35 ms
17,840 KB
testcase_39 AC 9 ms
5,048 KB
testcase_40 AC 26 ms
13,464 KB
testcase_41 AC 29 ms
15,228 KB
testcase_42 AC 36 ms
18,188 KB
testcase_43 AC 38 ms
19,528 KB
testcase_44 AC 386 ms
160,228 KB
testcase_45 AC 371 ms
160,212 KB
testcase_46 AC 377 ms
160,212 KB
testcase_47 AC 375 ms
160,256 KB
testcase_48 AC 382 ms
160,160 KB
testcase_49 AC 38 ms
19,548 KB
testcase_50 AC 39 ms
19,548 KB
testcase_51 AC 38 ms
19,532 KB
testcase_52 AC 38 ms
19,552 KB
testcase_53 AC 373 ms
160,244 KB
testcase_54 AC 378 ms
160,276 KB
testcase_55 AC 372 ms
160,160 KB
testcase_56 AC 364 ms
160,200 KB
testcase_57 AC 379 ms
160,300 KB
testcase_58 AC 371 ms
160,124 KB
testcase_59 AC 374 ms
160,208 KB
testcase_60 AC 376 ms
160,172 KB
testcase_61 AC 366 ms
160,280 KB
testcase_62 AC 376 ms
160,324 KB
testcase_63 AC 521 ms
34,708 KB
testcase_64 AC 573 ms
41,308 KB
testcase_65 AC 181 ms
41,320 KB
testcase_66 AC 582 ms
41,328 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