#P12542. [APIO2025] Permutation Game
[APIO2025] Permutation Game
题目描述
Alice and Bob are childhood friends, and they love playing intellectual games. Today, they are playing a new game on graphs.
The game set contains a connected graph with vertices, numbered from to , and edges, numbered from to . The -th edge connects vertices and .
The game set also contains a permutation of length , where . Permutation is an array in which each number from to appears exactly once, in some order. The score of permutation is the number of indices such that .
The game will last for at most turns. In each turn, the following happens:
- If Alice decides to end the game, the game stops.
- Otherwise, Alice chooses distinct indices , where . Note that, the game does not require .
- Bob chooses an index of the edges of the graph and swaps and .
Alice wishes to maximize the final score of the permutation while Bob wishes to minimize the final score of the permutation.
Your task is to help Alice and play against Bob, whose moves are simulated by grader.
Let's define optimal score as the final score of the permutation if both Alice and Bob play optimally.
You will need to determine the optimal score of the permutation and then play the game with Bob to achieve at least that optimal score after some turns.
Note that Alice's strategy should work no matter what moves Bob makes, including if Bob makes unoptimal moves.
Implementation details
You should implement the following procedure:
int Alice(int m, int e, std::vector<int> u, std::vector<int> v,
int n, std::vector<int> p)
m
: the number of vertices in the graph.e
: the number of edges in the graph.u
andv
: arrays of lengthe
describing the edges of the graph.n
: the length of the permutation.p
: an array of lengthn
describing the permutation.
This procedure is called exactly once. This procedure should return an integer – the optimal score of the game. Within this procedure, you may call the following procedure:
int Bob(std::vector<int> t)
t
: an array of sizem
, containing distinct indices, where and for any . This function returns a single integerj
which satisfies . This procedure can be called multiple times.
提示
Example
Consider the following call:
Alice(5, 6, [4, 0, 3, 1, 4, 2], [2, 2, 0, 2, 0, 3],
10, [8, 2, 7, 6, 1, 5, 0, 9, 3, 4])
The graph is as follows:
and p
is initially [8, 2, 7, 6, 1, 5, 0, 9, 3, 4]
.
Given the constraints above, we can prove that the optimal score of the permutation is 1
.
Suppose, Alice makes the following 4 moves:
Argument of t to Bob |
Return value of Bob | Corresponding indices of p |
p after the swap by Bob |
---|---|---|---|
[3, 1, 5, 2, 0] |
5 |
5, 2 |
[8, 2, 5, 6, 1, 7, 0, 9, 3, 4] |
[9, 3, 7, 2, 1] |
0 |
1, 7 |
[8, 9, 5, 6, 1, 7, 0, 2, 3, 4] |
[5, 6, 7, 8, 9] |
1 |
5, 7 |
[8, 9, 5, 6, 1, 2, 0, 7, 3, 4] |
[7, 5, 2, 3, 6] |
3 |
5, 2 |
[8, 9, 2, 6, 1, 5, 0, 7, 3, 4] |
Note that Alice and Bob not necessarily making the optimal moves. These moves are shown purely for demonstration purposes. Also note that Alice could finish the game immediately, as the initial score of the permutation is already 1
.
After Alice has performed all the moves above, the actual score of the permutation is 3
(, , ). Finally, the function Alice()
will return 1
– the optimal score of the permutation.
Note that even though Alice has achieved a score of 3 by playing with Bob, you would get 0 points if the return value of Alice()
was 3 instead of 1.
Constraints
- The graph is connected, contains no self-loops or multiple edges.
- is a permutation, i.e. for any .
Subtasks
- (6 points)
- (6 points)
- (10 points)
- (24 points)
- (24 points)
- (30 points)
For each subtask, you can get partial score. Let be the maximum ratio of among all test cases of a subtask, where is the number of turns (i.e. calls to Bob()
). Then, your score for that subtask is multiplied by the following number:
Condition | Multiplier |
---|---|
In particular, if you solve the problem within turns, you get full points for that subtask. Using more than turns results in getting 0 for that subtask (shown as Output isn't correct
).
Sample Grader
The sample grader reads the input in the following format:
- line 1:
- line 2 + ():
- line 2 + :
- line 3 + :
The sample grader prints the output in the following format:
- line 1: final permutation
- line 2: return value of
Alice()
- line 3: actual score of final permutation
- line 4: the number of turns