[solution] Infinite Card Game Solution Codeforces

E. Infinite Card Game
time limit per test

3 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Monocarp and Bicarp are playing a card game. Each card has two parameters: an attack value and a defence value. A card s beats another card t if the attack of s is strictly greater than the defence of t.

Monocarp has n cards, the i-th of them has an attack value of axi��� and a defence value of ayi���. Bicarp has m cards, the j-th of them has an attack value of bxj��� and a defence value of byj���.

On the first move, Monocarp chooses one of his cards and plays it. Bicarp has to respond with his own card that beats that card. After that, Monocarp has to respond with a card that beats Bicarp’s card. After that, it’s Bicarp’s turn, and so forth.

After a card is beaten, it returns to the hand of the player who played it. It implies that each player always has the same set of cards to play as at the start of the game. The game ends when the current player has no cards that beat the card which their opponent just played, and the current player loses.

If the game lasts for 100500100500 moves, it’s declared a draw.

Both Monocarp and Bicarp play optimally. That is, if a player has a winning strategy regardless of his opponent’s moves, he plays for a win. Otherwise, if he has a drawing strategy, he plays for a draw.

You are asked to calculate three values:

  • the number of Monocarp’s starting moves that result in a win for Monocarp;
  • the number of Monocarp’s starting moves that result in a draw;
  • the number of Monocarp’s starting moves that result in a win for Bicarp.
Input

The first line contains a single integer t (1t1041≤�≤104) — the number of test cases.

The first line of each test case contains an integer n (1n31051≤�≤3⋅105) — the number of cards Monocarp has.

The second line contains n integers ax1,ax2,,axn��1,��2,…,��� (1axi1061≤���≤106) — the attack values of Monocarp’s cards.

The third line contains n integers ay1,ay2,,ayn��1,��2,…,��� (1ayi1061≤���≤106) — the defence values of Monocarp’s cards.

The fourth line contains a single integer m (1m31051≤�≤3⋅105) — the number of cards Bicarp has.

The fifth line contains m integers bx1,bx2,,bxm��1,��2,…,��� (1bxj1061≤���≤106) — the attack values of Bicarp’s cards.

The sixth line contains m integers by1,by2,,bym��1,��2,…,��� (1byj1061≤���≤106) — the defence values of Bicarp’s cards.

Additional constraints on the input: the sum of n over all test cases doesn’t exceed 31053⋅105, the sum of m over all test cases doesn’t exceed 31053⋅105.

Output

For each test case, print three integers:

  • the number of Monocarp’s starting moves that result in a win for Monocarp;
  • the number of Monocarp’s starting moves that result in a draw;
  • the number of Monocarp’s starting moves that result in a win for Bicarp.
Example
input

Copy
3
3
8 7 4
7 1 10
2
8 4
5 10
9
8 8 5 5 5 4 4 1 4
2 7 5 2 8 9 7 1 9
10
9 8 7 6 5 5 4 3 2 1
7 1 6 7 5 8 8 4 9 6
1
10
5
1
10
5
output

Copy
1 1 1
2 4 3
0 1 0

solution

# Function to calculate the number of Monocarp’s starting moves that result in a win, draw, and loss
def calculate_moves_outcome(n, ax, ay, m, bx, by):
# Create a list of tuples (attack, defense)
player1 = [(ax[i], ay[i]) for i in range(n)]
player2 = [(bx[i], by[i]) for i in range(m)]

# Sort the lists by attack values in descending order
player1.sort(key=lambda x: -x[0])
player2.sort(key=lambda x: -x[0])

# Initialize counters for wins, draws, and losses
wins1, draws, wins2 = 0, 0, 0
j = 0 # Index for player2

for i in range(n):
while j < m and player1[i][0] > player2[j][1]:
j += 1
if j == m:
wins1 += (n – i) # Player1 wins all remaining moves
break
elif player1[i][0] < player2[j][1]:
draws += 1 # Player2 wins this move
else:
j += 1 # Player1 and Player2 draw this move

for i in range(j, m):
wins2 += 1 # Player2 wins all remaining moves

return wins1, draws, wins2

# Read the number of test cases
t = int(input())

# Iterate through each test case
for _ in range(t):
n = int(input())
ax = list(map(int, input().split()))
ay = list(map(int, input().split()))
m = int(input())
bx = list(map(int, input().split()))
by = list(map(int, input().split()))

# Calculate the number of wins, draws, and losses for Monocarp
wins1, draws, wins2 = calculate_moves_outcome(n, ax, ay, m, bx, by)

# Print the results for this test case
print(wins1, draws, wins2)

Leave a Comment