結果

問題 No.759 悪くない忘年会にしような！
コンテスト
ユーザー t33f
提出日時 2018-12-10 19:52:14
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 64
権限があれば一括ダウンロードができます

ソースコード

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