UVA 11134 Fabled Rooks ( 二維置點問題 )

UVa Online Judge
和這題是一樣的算法：
h0rnet.hatenablog.com
即使變二維，可以將水平座標和鉛直座標做拆解成為兩個相互獨立的置點問題。比較雷的是我忘記判斷優先佇列是空的時候，代表這個位置不能放任何東西，需要跳過，就吃了RE。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 3;

int n;

struct Rook{
    int id, l, r;
    bool operator < (const Rook &oth) const{
        return r > oth.r;
    } // pq pops least r
} rook[2][MAXN];

bool cmp_l(const Rook &a, const Rook &b){
    return a.l < b.l;
}

int ans[2][MAXN];

void solve(){
    bool fail = false;
    for(int k = 0; k < 2; ++k){
        sort( rook[ k ], rook[ k ] + n, cmp_l );
        priority_queue<Rook> pq;
        int cnt = 0;
        for(int i = 1; i <= n; ++i){
            while( cnt < n && rook[ k ][ cnt ].l <= i )
                pq.push( rook[ k ][ cnt++ ] );
            if( pq.empty() ) continue; // !!
            Rook c = pq.top(); pq.pop();
            if( c.r < i ){ fail = true; break; }
            ans[ k ][ c.id ] = i;
        }
        if( fail || cnt < n || !pq.empty() ){
            puts("IMPOSSIBLE");
            return;
        }
    }
    for(int i = 0; i < n; ++i)
        printf("%d %d\n", ans[0][i], ans[1][i]);
}

int main(){
    while( scanf("%d", &n) == 1 && n ){
        for(int i = 0; i < n; ++i){
            scanf("%d%d%d%d", &rook[0][i].l, &rook[1][i].l, &rook[0][i].r, &rook[1][i].r);
            rook[0][i].id = rook[1][i].id = i;
        }
        solve();
    }
    return 0;
}

我以前是用另一種寫法，現在覺得沒那麼泛用。以右界排序，相同時以長度排序( 右界越小越早消失，越短越需要把握，需要優先進行 )過後，對於每個點，從它的左界到右界掃描過去，放入第一個還沒被佔用的位置。現在想想，應該可以構造測資讓這個時間複雜度很慘。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000 + 5;

int n;
struct Car{
    int d1, d2, idx;
    bool operator < (const Car &b) const{
        if( d2 != b.d2 ) return d2 < b.d2;
        return d1 > b.d1;
    }   
}cx[MAXN], cy[MAXN];

bool visx[MAXN], visy[MAXN];
int ax[MAXN], ay[MAXN];
bool solve(){
    memset( visx, false, sizeof(visx) );
    memset( visy, false, sizeof(visy) );
    for(int i = 0; i < n; ++i){
        int dx, dy;
        for(dx = cx[i].d1; dx <= cx[i].d2; ++dx)
            if( !visx[dx] ) break;
        if( dx > cx[i].d2 ) return false;
        for(dy = cy[i].d1; dy <= cy[i].d2; ++dy)
            if( !visy[dy] ) break;
        if( dy > cy[i].d2 ) return false;
        visx[dx] = visy[dy] = true;
        int idx = cx[i].idx, idy = cy[i].idx;
        ax[ idx ] = dx, ay[ idy ] = dy;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    while( cin >> n && n ){
        for(int i = 0; i < n; ++i){
            cin >> cx[i].d1 >> cy[i].d1 >> cx[i].d2 >> cy[i].d2;
            cx[i].idx = cy[i].idx = i;
        }

        sort( cx, cx + n );
        sort( cy, cy + n );

        if( !solve() ) cout << "IMPOSSIBLE" << endl;
        else for(int i = 0; i < n; ++i)
                cout << ax[i] << ' ' << ay[i] << endl;
    }
    return 0;
}