知识点:贪心,
这道题首先第一步,就是看出结论,行列无关,行按照行的算,列按照列的算,然后发现这个其实就是区间贪心李煜东讲的那个模型,给定若干点和闭区间,一个点只能属于一个区间,怎么放能让更多的区间里面有点,具体到这道题,点就是1到n,点数和区间数相等,题目的意思就是能不能把这个n个点放到这些个区间里面,其实就是求最大被覆盖区间数,如果最大被覆盖区间数等于n,那么说明能,每个点都放到了一个对应的区间里面,那么这个维度上就是有解,判断无解也很简单,这种的思路就是外层遍历区间内层遍历点,如果有一个区间没有放进去点,那么它就是无解的,判断输出即可
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pa;
const int N = 5005;
struct point {
int x, y, rank;
} a[N], b[N];
int rec1[N], rec2[N];
bool cmp(point a, point b) {
return a.x > b.x;
}
int main() {
int n;
while (cin >> n && n) {
for (int i = 0; i < n; i++) {
cin >> a[i].x >> b[i].x >> a[i].y >> b[i].y;
a[i].rank = b[i].rank = i;
}
sort(a, a + n, cmp);
sort(b, b + n, cmp);
vi v1, v2;
for (int i = n; i >= 1; i--) { v1.pb(i); v2.pb(i); }
int ook = 1;
for (int i = 0; i < n; i++) {
int ok = 0;
for (int j = 0; j < sz(v1); j++) {
if (v1[j] <= a[i].y && v1[j] >= a[i].x) {
rec1[a[i].rank] = v1[j];
v1.erase(v1.begin() + j);
ok = 1; break;
}
}
if (!ok) { ook = 0; break; }
}
if (!ook) { cout << "IMPOSSIBLE" << endl; continue; }
for (int i = 0; i < n; i++) {
int ok = 0;
for (int j = 0; j < sz(v2); j++) {
if (v2[j] <= b[i].y && v2[j] >= b[i].x) {
rec2[b[i].rank] = v2[j];
v2.erase(v2.begin() + j);
ok = 1; break;
}
}
if (!ok) { ook = 0; break; }
}
if (!ook) { cout << "IMPOSSIBLE" << endl; continue; }
for (int i = 0; i < n; i++) cout << rec1[i] << " " << rec2[i] << endl;
}
return 0;
}