Color the Ball
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3502 Accepted Submission(s): 863
Problem Description
There are infinite balls in a line (numbered 1 2 3 ....), and initially all of them are paint black. Now Jim use a brush paint the balls, every time give two integers a b and follow by a char 'w' or 'b', 'w' denotes the ball from a to b are painted white, 'b' denotes that be painted black. You are ask to find the longest white ball sequence.
Input
First line is an integer N (<=2000), the times Jim paint, next N line contain a b c, c can be 'w' and 'b'.
There are multiple cases, process to the end of file.
Output
Two integers the left end of the longest white ball sequence and the right end of longest white ball sequence (If more than one output the small number one). All the input are less than 2^31-1. If no such sequence exists, output "Oh, my god".
Sample Input
3
1 4 w
8 11 w
3 5 b
Sample Output
8 11
Author
ZHOU, Kai
Source
ZOJ Monthly, February 2005
Recommend
Ignatius.L
First we should know which part is white in the end.The range of the balls' coordinate is too large for a boolean array.Fortunately ,there is a similar problem in USACO,which could be solved by floating method.Here,let each segment whose color is white float to top,and it is divide when it bump into a black one.Then the part remain is a white segment in the end.
Sort the white segment by their begin point.For the segment from 2 to T,combine it with its previous one if they have common.Then the longest element should be the answer.
#include<stdio.h>
#include<string.h>
class edge
{
public:
int l,r;
};
int N,T;
int a[2025],b[2025];
char col[2025];
edge E[1000000];
int Max(int x,int y)
{
return x>y ? x:y;
}
int Min(int x,int y)
{
return x<y ? x:y;
}
void dfs(int l,int r,int dep)
{
if (dep==N)
{
T++;
E[T].l=l;
E[T].r=r;
return;
}
if (col[dep+1]=='w') dfs(l,r,dep+1);
else
{
if (l<a[dep+1]) dfs(l,Min(r,a[dep+1]-1),dep+1);
if (b[dep+1]<r) dfs(Max(b[dep+1]+1,l),r,dep+1);
}
}
void qsort(int l,int r)
{
int i=l,j=r,x=E[(l+r)>>1].l;
do
{
while (E[i].l<x) i++;
while (x<E[j].l) j--;
if (i<=j)
{
edge tmp=E[i];
E[i]=E[j];
E[j]=tmp;
i++;
j--;
}
}
while (i<=j);
if (i<r) qsort(i,r);
if (l<j) qsort(l,j);
}
int main()
{
while (scanf("%d",&N)!=EOF)
{
int i;
for (i=1;i<=N;i++)
{
scanf("%d %d %c",&a[i],&b[i],&col[i]);
if (a[i]>b[i])
{
int t=a[i];
a[i]=b[i];
b[i]=t;
}
}
T=0;
for (i=1;i<=N;i++)
if (col[i]=='w') dfs(a[i],b[i],i);
qsort(1,T);
for (i=2;i<=T;i++)
if (E[i-1].l<=E[i].l && E[i].l<=E[i-1].r+1)
{
if (E[i-1].l<E[i].l) E[i].l=E[i-1].l;
if (E[i].r<E[i-1].r) E[i].r=E[i-1].r;
}
if (T==0)
{
printf("Oh, my god
");
continue;
}
int MAX=0;
for (i=1;i<=T;i++)
if (E[i].r-E[i].l+1>MAX) MAX=E[i].r-E[i].l+1;
for (i=1;i<=T;i++)
if (E[i].r-E[i].l+1==MAX)
{
printf("%d %d
",E[i].l,E[i].r);
break;
}
}
return 0;
}