Cod sursă (job #195667)

#include <cassert>
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
#define x first.first
#define y first.second
#define z second.first
#define t second.second
const int NMAX = 2050;
ifstream fin("canibali.in");
ofstream fout("canibali.out");
vector<pair<pair<int, int>, pair<int, int> > > V(NMAX);
vector<int> G[NMAX << 1], L(NMAX << 1, -1), R(NMAX, -1);
bitset<NMAX << 1> vis;
int N, paired;
inline bool canEat(int eater, int eaten) {
return (V[eater].x >= V[eaten].x && V[eater].y >= V[eaten].y && V[eater].z >= V[eaten].z && V[eater].t > V[eaten].t);
}
inline bool canEatMutual(int eater, int eaten) {
return (V[eater].x == V[eaten].x && V[eater].y == V[eaten].y && V[eater].z == V[eaten].z && V[eater].t == V[eaten].t);
}
inline bool pairUp(int node) {
if (vis[node])
return false;
vis[node] = true;
for (vector<int>::iterator i = G[node].begin(); i != G[node].end(); ++i)
if (R[*i] == -1) {
L[node] = *i;
R[*i] = node;
return true;
}
for (vector<int>::iterator i = G[node].begin(); i != G[node].end(); ++i)
if (pairUp(R[*i])) {
L[node] = *i;
R[*i] = node;
return true;
}
return 0;

}
int main() {
fin >> N;
assert(1 <= N && N <= 2048);
for (int i = 0; i < N; ++i) {
fin >> V[i].x >> V[i].y >> V[i].z >> V[i].t;
assert(0 <= V[i].x && V[i].x <= 131072);
assert(0 <= V[i].y && V[i].y <= 131072);
assert(0 <= V[i].z && V[i].z <= 131072);
assert(0 <= V[i].t && V[i].t <= 131072);
}
for (int i = 0; i < N; ++i) {



for (int j = 0; j < N; ++j)
if (canEatMutual(i, j)) {
if (i < j) {
G[i].push_back(j);
G[i + N].push_back(j);
}
}
else if (canEat(i, j)) {
G[i].push_back(j);
G[i + N].push_back(j);
}
}
bool done;
do {
done = true;
vis.reset();
for (int i = 0; i < (N << 1); ++i)
if (L[i] < 0 && pairUp(i)) {
done = false;
++paired;
}
}
while (!done);
fout << N - paired << "\n";


return 0;
}