BOJ 8103 - Rooks

문제 링크 : https://www.acmicpc.net/problem/8103

문제 풀이

 가능한 위치가 직사각형으로 주어진다. 직사각형이기 때문에  y 좌표가 가능한 범위는 x 좌표에 영향을 받지 않는다. 따라서 x와 y를 따로 놓고 생각해서 구할 수 있다. 주어진 문제를 축 별로 쪼개서 본다고 하면, 구간이 n개 주어지고 n개의 구간에서 각각 수를 하나 씩 뽑아야 하는데 이 수가 1~n까지 서로 다른 수여야 한다. 

 위의 문제를 어떻게 풀 수 있을까? 이미 1~i-1 까지 배정을 했다고 하자. 이제 i를 어떤 구간에다가 배정해야 할 지 골라야 한다. 가능한 구간은 s~e에서 s가 i보다 작으며, e가 i보다 큰 구간들이다. 이러한 구간들에서 e가 가장 작은 구간을 뽑는 것이 이득이다. 앞으로 가능한 구간은 i~e 이기 때문에 e가 더 큰 구간은 가능한 경우가 e가 더 작은 구간을 포함하게 된다. 따라서 항상 가능한 구간들 중 그리디하게 e가 가장 작은 구간을 배정하는 것이 옳다. 
 구간을 빼고 넣으면서 가능한 구간을 e가 작은 순서대로 들고 있는 것은 pq를 쓰면 할 수 있다. 따라서 전체 문제를 $O(NlgN)$ 에 해결할 수 있으며, 문제에서 제공한 제한 3000은 굉장히 이에 비해서 작은 값이다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef double dl;
typedef pair<dl,dl> pdi;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
 
#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
//cout<<fixed;
//cout.precision(12);
 
struct poi{
    ll idx,s,e;
};
 
struct sf1{
    bool operator()(poi a,poi b){
        return a.e>b.e;
    }
};
 
bool sf(poi a,poi b){
    return a.s<b.s;
}
 
vector<ll> x;
ll n,m;
ll mod=998244353;
string s;
string t;
poi ax[1010101];
poi bx[1010101];
ll ansa[1010101];
ll ansb[1010101];
 
vector<ll> v[1010101];
priority_queue<poi,vector<poi>,sf1> pqa;
priority_queue<poi,vector<poi>,sf1> pqb;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll i,j,k,a,b,c,d,e,f;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>ax[i].s;
        cin>>bx[i].s;
        cin>>ax[i].e;
        cin>>bx[i].e;
        ax[i].idx=bx[i].idx=i;
    }
    sort(ax+1,ax+1+n,sf);
    sort(bx+1,bx+1+n,sf);
 
    ll fla=1;
    ll flb=1;
    for(i=1;i<=n;i++){
        while(ax[fla].s==i){
            pqa.push(ax[fla]);
            fla++;
        }
        if(pqa.empty()){
            cout<<"NIE";
            return 0;
        }
        auto x=pqa.top();
        //cout<<i<<' '<<x.idx<<'\n';
        if(x.e<i){
            cout<<"NIE";
            return 0;
        }
        pqa.pop();
        ansa[x.idx]=i;
 
        while(bx[flb].s==i){
            pqb.push(bx[flb]);
            flb++;
        }
        if(pqb.empty()){
            cout<<"NIE";
            return 0;
        }
        x=pqb.top();
        if(x.e<i){
            cout<<"NIE";
            return 0;
        }
        pqb.pop();
        ansb[x.idx]=i;
        //cout<<i<<' '<<x.idx<<'\n';
    }
 
    for(i=1;i<=n;i++){
        cout<<ansa[i]<<' '<<ansb[i]<<'\n';
    }
}