22919번 - Ropes 서브태스크다국어인터랙티브채점 준비 중

Two scout teams are taking part in a scouting competition. It is the finals and each team is well prepared. The game is played along a river that flows west to east. There are 4N trees planted along the river, with exactly 2N of them lined up along the north bank and 2N lined up along the south bank. Both teams alternate turns playing the game. Your team goes first.

On each turn, the playing team selects one tree on each bank that does not have any ropes tied to it and ties a rope between both trees, making it cross the river. Each rope that is added is placed higher than all previous ropes. The playing team scores 1 point per each previously used rope that passes below the newly added rope.

After 2N turns, all trees have exactly one rope tied to them, so there are no more possible plays and the game is over. The score of each team is the sum of the scores they got in all of their turns. If your team's score is strictly greater than the opposing team's score, your team wins. If your team's score is less than or equal to the opposing team's score, your team does not win.

The following animation shows a possible game with N=2. Your team is represented by the color red and the other team by the color blue.

The opposing team felt confident that going second is a large advantage, so they revealed their strategy. On their turn, they choose the play that yields the maximum possible score for this turn. If multiple such plays exist, they choose one at random. This choice is generated uniformly at random, and independently for each play, for each test case and for each submission. Therefore, even if you submit exactly the same code twice, the opposing team can make different random choices.

You play T games in total, and your team must win at least W of them.

This is an interactive problem.

Initially, your program should read a single line containing three integers T, N, and W: the number of test cases, the number of turns of your team and the number of wins you need to get for your solution to be considered correct, respectively. Note that the opposing team also gets N turns, for a total of 2N turns for each test case.

For each test case, your program must process N exchanges. Each exchange represents two consecutive turns, one from your team and one from the opposing team.

For the i⁠-⁠th exchange, you must first print a single line with two integers A_i and B_i and then read a single line with two integers C_i and D_i. This represents that in your i⁠-⁠th turn you tied the rope between the A_i-⁠th tree from the west on the north bank and the B_i⁠-⁠th tree from the west on the south bank. Similarly, in the opposing team's i⁠-⁠th turn they used the Ci⁠-⁠th tree from the west on the north bank and the D_i-⁠th tree from the west on the south bank. Trees are indexed starting from 1.

After the N exchanges, you must read one number that represents the result of this game. This number will be 1 if your team won, otherwise it will be 0.

The next test case starts immediately if there is one. If this was the last test case, the judge will expect no more output and will send no further input to your program. In addition, all T test cases are always processed, regardless of whether it is already guaranteed that the threshold for correctness will or cannot be met. The threshold is only checked after correctly processing all test cases.

If the judge receives an invalidly formatted line or invalid move (like using a tree that has already been used) from your program at any moment, the judge will print a single number -1 and will not print any further output. If your program continues to wait for the judge after receiving a -1, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error. As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment.

• T = 2000.
• N = 50.

• W = 1200 (W = 0.6 ⋅ T).

• W = 1560 (W = 0.78 ⋅ T).

• W = 1720 (W = 0.86 ⋅ T).

• local_testing_tool.py