Tenis
레이팅 미적용의견: 0
Mirko is a big fan of tennis. Soon an important tournament with \(n\) players will take place. Mirko has
spent years researching tennis players and has collected various statistics about the competitors. He has
ranked their ability on three different courts: grass, clay and hard. More precisely, for each court he has
determined the order (rank list) of the players, with the first player being the strongest, and the last being
the weakest.
On this tournament, every player will play against every other player exactly once, so there will be {n}{n}}^{1)
2
matches in total. A tennis match cannot end in a draw, and the player who is stronger on the court
the match is played on will win. The organisers know that, so they have decided that each match
should be played on the court for which the winner will be the strongest, i.e. have the best position in the
corresponding rank list. If some courts are equal in that sense (the position of the winner of the match
between players \(A\) and \(B\) would be the same, e.g. player \(A\) would win on court 1, and player \(B\) on court
2, and they are both ranked third on the corresponding court rank lists), they will choose the court for
which the loser would have the best position. If the courts are still equal, the one with the smallest index
is chosen.
Determine the outcome of this tournament: the number of matches played on each court and the number
of wins for each player.
Subtask 1 (35 points): \(1 \le n \le 300\)
Subtask 2 (15 points): \(1 \le n \le 3000\)
Subtask 3 (60 points): \(1 \le n \le 100\,000\) If your solution prints at least one of the lines correctly on each test case of a subtask, but it doesn’t print both lines correctly on at least one test case, you will get half of the points for that subtask.
The first line contains an integer \(n\), the number of players. The players are labeled with integers from 1 to
\(n\).
The \(i-th\) of the following three lines contains a permutation of integers from 1 to \(n\), the rank list of the
players for the \(i-th\) surface, starting with the strongest player.
In the first line, print the number of matches played on the first, second and third surface.
In the second line, print the number of matches won by each player from 1 to \(n\).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 35점 | \(1 \le n \le 300\) |
2 | 15점 | \(1 \le n \le 3000\) |
3 | 60점 | \(1 \le n \le 100\,000\) If your solution prints at least one of the lines correctly on each test case of a subtask, but it doesn’t print both lines correctly on at least one test case, you will get half of the points for that subtask. |
3
3 2 1
1 3 2
3 2 1
1 2 0
2 0 1
4
4 3 2 1
3 1 2 4
1 2 3 4
3 2 1
1 0 2 3
평가 및 의견
Tenis
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Tenis