首页 > 代码库 > 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 }
View Code