Mice and Rice is the name of a programming contest in which each programmer must write a piece of code to control the movements of a mouse in a given map. The goal of each mouse is to eat as much rice as possible in order to become a FatMouse.
First the playing order is randomly decided for N P programmers. Then every N G programmers are grouped in a match. The fattest mouse in a group wins and enters the next turn. All the losers in this turn are ranked the same. Every N G winners are then grouped in the next match until a final winner is determined.
For the sake of simplicity, assume that the weight of each mouse is fixed once the programmer submits his/her code. Given the weights of all the mice and the initial playing order, you are supposed to output the ranks for the programmers.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers: N P and N G (<= 1000), the number of programmers and the maximum number of mice in a group, respectively. If there are less than N G mice at the end of the player's list, then all the mice left will be put into the last group. The second line contains N P distinct non-negative numbers W i (i=0,...N P -1) where each W i is the weight of the i-th mouse respectively. The third line gives the initial playing order which is a permutation of 0,...N P -1 (assume that the programmers are numbered from 0 to N P -1). All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the final ranks in a line. The i-th number is the rank of the i-th programmer, and all the numbers must be separated by a space, with no extra space at the end of the line.
Sample Input:
11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3
Sample Output:
5 5 5 2 5 5 5 3 1 3 5
1
#include<stdio.h>
2
#include<vector>
3
#include<map>
4
#include<algorithm>
5
using
namespace
std;
6
7
struct
MyStruct
8
{
9
int
ID;
10
int
wight;
11
};
12
13
struct
MyRank
14
{
15
int
time;
16
int
ID;
17
};
18
19
vector<MyRank>
ranking;
20
21
void
fun(vector<MyStruct> vv ,
int
Ng)
22
{
23
vector<MyStruct>
tem;
24
for
(
int
i =
0
;i< vv.size(); i++
)
25
{
26
if
( i + Ng -
1
<
vv.size())
27
{
28
int
MAX = -
1
;
29
int
index;
30
int
j;
31
for
(j = i ;j < i + Ng ;j++
)
32
{
33
if
(vv[j].wight >
MAX)
34
{
35
MAX =
vv[j].wight;
36
index =
j;
37
}
38
}
39
i = j-
1
;
40
tem.push_back(vv[index]);
41
++
ranking[vv[index].ID].time;
42
}
43
else
44
{
45
int
MAX = -
1
;
46
int
index;
47
int
j;
48
for
(j = i ;j < vv.size() ;j++
)
49
{
50
if
(vv[j].wight >
MAX)
51
{
52
MAX =
vv[j].wight;
53
index =
j;
54
}
55
}
56
i =
j;
57
tem.push_back(vv[index]);
58
++
ranking[vv[index].ID].time;
59
}
60
}
61
62
if
(tem.size() >
1
)
63
fun(tem,Ng);
64
}
65
66
int
cmp(MyRank a,MyRank b)
67
{
68
return
a.time >
b.time ;
69
}
70
71
int
main()
72
{
73
int
Np,Ng,i;
74
MyStruct tem;
75
MyRank Rtem;
76
int
index;
77
scanf(
"
%d%d
"
,&Np,&
Ng);
78
vector<MyStruct>
v1,v2;
79
for
(i =
0
;i< Np ;i++
)
80
{
81
scanf(
"
%d
"
,&
tem.wight);
82
tem.ID =
i;
83
Rtem.ID =
i;
84
Rtem.time =
0
;
85
ranking.push_back(Rtem);
86
v1.push_back(tem);
87
}
88
for
(i =
0
;i< Np ;i++
)
89
{
90
scanf(
"
%d
"
,&
index);
91
v2.push_back(v1[index]);
92
}
93
94
fun(v2,Ng);
95
96
sort(ranking.begin(),ranking.end(),cmp);
97
int
result[
1001
];
98
int
j =
1
;
99
for
(i =
0
;i <ranking.size();i++
)
100
{
101
result[ranking[i].ID] =
j;
102
int
count =
1
;
103
int
tem =
ranking[i].time;
104
while
(i+
1
<ranking.size()&&tem == ranking[i+
1
].time)
105
{
106
++
i;
107
++
count;
108
result[ranking[i].ID] =
j;
109
}
110
j = j+
count;
111
}
112
113
for
(i =
0
;i < Np ;i++
)
114
{
115
if
(i ==
0
) printf(
"
%d
"
,result[i]);
116
else
printf(
"
%d
"
,result[i]);
117
}
118
printf(
"
\n
"
);
119
return
0
;
120
}
