当前位置: 代码迷 >> 综合 >> UVA 11134 Fabled Rooks .
  详细解决方案

UVA 11134 Fabled Rooks .

热度:106   发布时间:2023-09-23 05:16:27.0

题目地址:http://vjudge.net/problem/UVA-11134

第二次

[a,b]  区间排序的时候,b小的优先,因为是从左往右放的,首先把b小的放完

如[1,3],[1,4],[2,3],[2,3] 只有以b小为优先才行,a小为优先是不行的

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=5000+5;
int n;
struct Aug
{int a,b,idx;bool operator < (const Aug& src) const {if(b==src.b) return a<src.a;return b<src.b;}
}x[maxn],y[maxn];
int AnsX[maxn],AnsY[maxn];
bool done[maxn];
bool solve(Aug* A){sort(A+1,A+n+1);memset(done,false,sizeof(done));REP(i,1,n) {int p=-1;REP(j,A[i].a,A[i].b) if(!done[j]) {p=j;done[j]=true;break;}if(p==-1) return false;if(x==A) AnsX[A[i].idx]=p;else     AnsY[A[i].idx]=p;}return true;
}
int main(int argc, char const *argv[])
{while(scanf("%d",&n)==1&&n){REP(i,1,n) scanf("%d%d%d%d",&x[i].a,&y[i].a,&x[i].b,&y[i].b),x[i].idx=y[i].idx=i;if(!(solve(x)&&solve(y))) printf("IMPOSSIBLE\n");else REP(i,1,n) printf("%d %d\n", AnsX[i],AnsY[i]);}return 0;
}