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 }

uva 11143

时间: 06-23

uva 11143的相关文章

UVA 562 Dividing coins --01背包的变形

01背包的变形. 先算出硬币面值的总和,然后此题变成求背包容量为V=sum/2时,能装的最多的硬币,然后将剩余的面值和它相减取一个绝对值就是最小的差值. 代码: #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define N 50007 int c[102],d

UVA 10341 Solve It

Problem F Solve It Input: standard input Output: standard output Time Limit: 1 second Memory Limit: 32 MB Solve the equation: p*e-x + q*sin(x) + r*cos(x) + s*tan(x) + t*x2 + u = 0 where 0 <= x <= 1. Input Input consists of multiple test cases and te

UVA 11014 - Make a Crystal(容斥原理)

UVA 11014 - Make a Crystal 题目链接 题意:给定一个NxNxN的正方体,求出最多能选几个整数点.使得随意两点PQ不会使PQO共线. 思路:利用容斥原理,设f(k)为点(x, y, z)三点都为k的倍数的点的个数(要扣掉一个原点O).那么全部点就是f(1),之后要去除掉共线的,就是扣掉f(2), f(3), f(5)..f(n).n为素数.由于这些素数中包括了合数的情况,而且这些点必定与f(1)除去这些点以外的点共线,所以扣掉.可是扣掉后会扣掉一些反复的.比方f(6)在f

[UVa] Palindromes(401)

UVA - 401 Palindromes Time Limit: 3000MS   Memory Limit: Unknown   64bit IO Format: %lld & %llu Submit Status Description A regular palindrome is a string of numbers or letters that is the same forward as backward. For example, the string "ABCDED

uva 401.Palindromes

题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=342 题目意思:给出一段字符串(大写字母+数字组成).判断是否为回文串 or 镜像串 or 回文镜像串 or 什么都不是.每个字母的镜像表格如下 Character Reverse Character Reverse Character Reverse A A M M Y Y B

[2016-02-19][UVA][129][Krypton Factor]

UVA - 129 Krypton Factor Time Limit: 3000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu Submit Status Description You have been employed by the organisers of a Super Krypton Factor Contest in which contestants have very high mental and physica

[2016-02-03][UVA][514][Rails]

时间:2016-02-03 22:24:52 星期三 题目编号:UVA 514 题目大意:给定若干的火车(编号1-n),按1-n的顺序进入车站, 给出火车出站的顺序,问是否有可能存在 分析:    FIFO,用栈模拟一遍即可, 方法:    根据输入的顺序,从1-n开始,当前操作的为i 如果i是当前对应的编号,那么直接跳过(进入B) 如果不是,根据当前需求的编号,小于i,就从栈顶弹出一个元素, 看这个元素是否是需求的,是则继续.否则NO 1 2 3 4 5 6 7 8 9 10 11 12 13

uva 11584 Partitioning by Palindromes 线性dp

// uva 11584 Partitioning by Palindromes 线性dp // // 题目意思是将一个字符串划分成尽量少的回文串 // // f[i]表示前i个字符能化成最少的回文串的数目 // // f[i] = min(f[i],f[j-1] + 1(j到i是回文串)) // // 这道题还是挺简单的,继续练 #include <algorithm> #include <bitset> #include <cassert> #include <

uva 10003 Cutting Sticks 简单区间dp

// uva 10003 Cutting Sticks 区间dp // 经典的区间dp // dp(i,j)表示切割小木棍i-j所需要的最小花费 // 则状态转移为dp(i,j) = min{dp(i,k) + dp(k,j) + a[j]-a[i]) // 其中k>i && k<j // a[j] - a[i] 为第一刀切割的代价 // a[0] = 0,a[n+1] = L; // dp数组初始化的时候dp[i][i+1]的值为 0,这表示 // 每一段都已经是切割了的,不