Cod sursă (job #143269)

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <cassert>

using namespace std;

const int MAXN = 1 << 11;

int X[MAXN], Y[MAXN], Z[MAXN], T[MAXN];
vector <int> G[MAXN];
int visited[MAXN];
int dead[MAXN];
int dfanswer = 0;

inline bool can_eat(int i, int j) {
    return (X[i] >= X[j] && Y[i] >= Y[j] && Z[i] >= Z[j] && T[i] >= T[j]);
}
void DFS(int node) {
    visited[node] = true;

    for (auto &it : G[node]) {
        if (!visited[it]) {
            DFS(it);
        }
    }

    if (dead[node]) {
        return ;
    }
    int x = 0;

    for (int i = 0; i < G[node].size() && x < 2; ++i) {
        if (dead[ G[node][i] ] == 0) {
            dead[ G[node][i] ] = 1;
            x += 1;
        }
    }
    random_shuffle(G[node].begin(), G[node].end());
    dfanswer += x;
}
int main() {

    ifstream cin("canibali.in");
    ofstream cout("canibali.out");

    int N; cin >> N;

    assert(3 <= N && N <= (1 << 11));

    for (int i = 0; i < N; ++i) {
        assert(cin >> X[i] >> Y[i] >> Z[i] >> T[i]);
        assert(0 <= X[i] && X[i] <= (1 << 17) );
        assert(0 <= Y[i] && Y[i] <= (1 << 17) );
        assert(0 <= Z[i] && Z[i] <= (1 << 17) );
        assert(0 <= T[i] && T[i] <= (1 << 17) );
    }

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i == j) {
                continue;
            }
            if (can_eat(i, j)) {
                G[i].push_back(j);
            }
        }
    }

    vector <int> perm(N);
    for (int i = 0; i < N; ++i) {
        perm[i] = i;
    }

    int solution = N;

    srand(time(NULL));
    for (int times = 0; times < 4000; ++times) {

        random_shuffle(perm.begin(), perm.end());

        dfanswer = 0;
        for (int i = 0; i < N; ++i) {
            dead[i] = 0;
        }

        for (int i = 0; i < N; ++i) {
            if (!visited[perm[i]]) {
                DFS(perm[i]);
            }
        }
        solution = min(solution, N - dfanswer);
    }
    cout << solution << "\n";

    return 0;
}