2015
05-24

# Throw nails

The annual school bicycle contest started. ZL is a student in this school. He is so boring because he can’t ride a bike!! So he decided to interfere with the contest. He has got the players’ information by previous contest video. A player can run F meters the first second, and then can run S meters every second.
Each player has a single straight runway. And ZL will throw a nail every second end to the farthest player’s runway. After the "BOOM", this player will be eliminated. If more then one players are NO.1, he always choose the player who has the smallest ID.

In the first line there is an integer T (T <= 20), indicates the number of test cases.
In each case, the first line contains one integer n (1 <= n <= 50000), which is the number of the players.
Then n lines follow, each contains two integers Fi(0 <= Fi <= 500), Si (0 < Si <= 100) of the ith player. Fi is the way can be run in first second and Si is the speed after one second .i is the player’s ID start from 1.
Hint

Huge input, scanf is recommended.
Huge output, printf is recommended.

In the first line there is an integer T (T <= 20), indicates the number of test cases.
In each case, the first line contains one integer n (1 <= n <= 50000), which is the number of the players.
Then n lines follow, each contains two integers Fi(0 <= Fi <= 500), Si (0 < Si <= 100) of the ith player. Fi is the way can be run in first second and Si is the speed after one second .i is the player’s ID start from 1.
Hint

Huge input, scanf is recommended.
Huge output, printf is recommended.

2
3
100 1
100 2
3 100
5
1 1
2 2
3 3
4 1
3 4

Case #1:
1 3 2
Case #2:
4 5 3 2 1

Hint
Hint
The first case:

1st Second end
Player1  100m    (BOOM!!)
Player2  100m
Player3    3m

2nd Second end
Player2  102m
Player3  103m    (BOOM!!)

3rd  Second end
Player2  104m    (BOOM!!)


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
struct node
{
int f,id;
bool operator<(const node& b)const
{
return (f<b.f)||(f==b.f && id>b.id);
}
};
priority_queue<node> s[120];
int sec,n;
int main()
{
scanf("%d",&sec);
for(int z=1;z<=sec;z++)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
node t;int f,d;
scanf("%d%d",&f,&d);
t.f=f;
t.id=i;
s[d].push(t);
}

printf("Case #%d:\n",z);
for(int i=1;i<=n;i++)
{
int maxx=-1,minid=1<<28;int re;
for(int j=1;j<=100;j++)
if(!s[j].empty())
{
node t=s[j].top();
if((i-1)*j+t.f>maxx || ((i-1)*j+t.f==maxx && t.id<minid))
{
maxx=(i-1)*j+t.f;
re=j;
minid=t.id;
}
}
int tem=s[re].top().id;
if(i==n)printf("%d\n",tem);else printf("%d ",tem);
s[re].pop();
}
}
return 0;
}