首页 > 代码库 > uva 11143
uva 11143
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define maxn 5100 5 #include<queue> 6 using namespace std; 7 8 struct node 9 { 10 int x,y; 11 int id; 12 bool operator<(const node &t)const 13 { 14 return y>t.y; 15 } 16 } hang[maxn],lie[maxn]; 17 18 bool cmp(const node &a,const node &b) 19 { 20 return a.x<b.x; 21 } 22 23 int h[maxn],l[maxn]; 24 25 priority_queue<node>q; 26 27 int main() 28 { 29 int n; 30 while(scanf("%d",&n)&&n) 31 { 32 for(int i=0; i<n; i++) 33 { 34 scanf("%d%d%d%d",&hang[i].x,&lie[i].x,&hang[i].y,&lie[i].y); 35 hang[i].id=lie[i].id=i; 36 h[i]=0; 37 l[i]=0; 38 } 39 sort(hang,hang+n,cmp); 40 int cur=0; 41 int timer=1; 42 bool flag=1; 43 while(!q.empty())q.pop(); 44 while(1) 45 { 46 while(cur<n&&hang[cur].x<=timer)q.push(hang[cur++]); 47 if(timer<=n&&q.empty()) 48 { 49 flag=0; 50 break; 51 } 52 node v=q.top(); 53 q.pop(); 54 if(timer<v.x||timer>v.y) 55 { 56 flag=0; 57 break; 58 } 59 h[v.id]=timer; 60 timer++; 61 if(timer>n)break; 62 } 63 if(flag) 64 { 65 sort(lie,lie+n,cmp); 66 cur=0; 67 timer=1; 68 while(!q.empty())q.pop(); 69 while(1) 70 { 71 while(cur<n&&lie[cur].x<=timer)q.push(lie[cur++]); 72 if(timer<=n&&q.empty()) 73 { 74 flag=0; 75 break; 76 } 77 node v=q.top(); 78 q.pop(); 79 if(timer<v.x||timer>v.y) 80 { 81 flag=0; 82 break; 83 } 84 l[v.id]=timer; 85 timer++; 86 if(timer>n)break; 87 } 88 } 89 for(int i=0;i<n;i++) 90 if(l[i]==0||h[i]==0) 91 { 92 flag=0; 93 break; 94 } 95 if(flag) 96 { 97 for(int i=0; i<n; i++) 98 printf("%d %d\n",h[i],l[i]); 99 }100 else puts("IMPOSSIBLE");101 }102 return 0;103 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。