uva11134 Fabled Rooks

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=100977#problem/D

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=(1<<29);

int n;
struct Rec
{
    int xl,yl,xr,yr;
    int id;
    void read(int ID)
    {
        scanf("%d%d%d%d",&xl,&yl,&xr,&yr);
        id=ID;
    }
};Rec rec[maxn];
struct Seg
{
    int l,r;
    int id;
    friend bool operator<(Seg A,Seg B)
    {
        return !(A.l==B.l?A.r<B.r:A.l<B.l);
    }
};Seg seg[maxn];
struct Point
{
    int x,y;
};Point ans[maxn];

int main()
{
    freopen("in.txt","r",stdin);
    while(cin>>n,n){
        REP(i,1,n) rec[i].read(i);
        REP(i,1,n) seg[i]={rec[i].xl,rec[i].xr,i};
        priority_queue<Seg> q;
        REP(i,1,n) q.push(seg[i]);
        bool flag=1;
        REP(i,1,n){
            priority_queue<Seg> qt;
            while(!q.empty()&&q.top().l<=i&&i<=q.top().r){
                qt.push(q.top());
                q.pop();
            }
            if(qt.empty()){
                flag=0;break;
            }
            Seg t=qt.top();qt.pop();
            ans[t.id].x=i;
            while(!qt.empty()){
                Seg it=qt.top();
                qt.pop();
                it.l=i+1;
                q.push(it);
            }
        }
        while(!q.empty()) q.pop();
        REP(i,1,n) seg[i]={rec[i].yl,rec[i].yr,i};
        REP(i,1,n) q.push(seg[i]);
        REP(i,1,n){
            priority_queue<Seg> qt;
            while(!q.empty()&&q.top().l<=i&&i<=q.top().r){
                qt.push(q.top());
                q.pop();
            }
            if(qt.empty()){
                flag=0;break;
            }
            Seg t=qt.top();qt.pop();
            ans[t.id].y=i;
            while(!qt.empty()){
                Seg it=qt.top();
                qt.pop();
                it.l=i+1;
                q.push(it);
            }
        }
        if(flag) REP(i,1,n) printf("%d %d
",ans[i].x,ans[i].y);
        else puts("IMPOSSIBLE");
    }
    return 0;
}
/**
题意：
    给定n个车的可放区域(矩形)，求将n个车在棋盘的不同位置，是之不能相互攻击且攻击范围覆盖整个棋盘(n*n)。
分析：
    显然,横坐标和纵坐标是相互独立的，所以分开处理。
    问题转化为在[1,n]中选n个不同的数，使之覆盖给定的n个区间。
    自然想到了贪心，先按左端点排序，再按右端点排序，发现还是用优先队列去维护，从左往右遍历点i，
    每次点i让覆盖到的区间全部出队，选择右端点最小的作为点i的覆盖区间，其余区间的左端点设为i+1，
    然后送回队列。
类型：
    贪心。
注意事项：
    贪心策略的选择。
坑点：
    无。
总结：
    不要看到贪心就只想着排序，也可以优先队列来维护贪心策略。
*/