Infinite Card Game (Codeforces 1895E)
Tags: Greedy, games

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 $$$\mathit{ax}_i$$$ and a defence value of $$$\mathit{ay}_i$$$. Bicarp has $$$m$$$ cards, the $$$j$$$-th of them has an attack value of $$$\mathit{bx}_j$$$ and a defence value of $$$\mathit{by}_j$$$.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 $$$100^{500}$$$ 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$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of cards Monocarp has.The second line contains $$$n$$$ integers $$$\mathit{ax}_1, \mathit{ax}_2, \dots, \mathit{ax}_n$$$ ($$$1 \le \mathit{ax}_i \le 10^6$$$) — the attack values of Monocarp's cards.The third line contains $$$n$$$ integers $$$\mathit{ay}_1, \mathit{ay}_2, \dots, \mathit{ay}_n$$$ ($$$1 \le \mathit{ay}_i \le 10^6$$$) — the defence values of Monocarp's cards.The fourth line contains a single integer $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — the number of cards Bicarp has.The fifth line contains $$$m$$$ integers $$$\mathit{bx}_1, \mathit{bx}_2, \dots, \mathit{bx}_m$$$ ($$$1 \le \mathit{bx}_j \le 10^6$$$) — the attack values of Bicarp's cards.The sixth line contains $$$m$$$ integers $$$\mathit{by}_1, \mathit{by}_2, \dots, \mathit{by}_m$$$ ($$$1 \le \mathit{by}_j \le 10^6$$$) — the defence values of Bicarp's cards.Additional constraints on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$, the sum of $$$m$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

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. 


Sample Inputs:
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

Sample Outputs:
1 1 1
2 4 3
0 1 0

Solution (Python):
import sys
input = sys.stdin.readline
import heapq

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, ax, ay, m, bx, by) = (readInt(), readList(), readList(), readInt(), readList(), readList())
    graph = [-1] * (n + m)
    (ai, bi) = ([i for i in range(n)], [i for i in range(m)])
    ai.sort(key=lambda x: -ay[x])
    bi.sort(key=lambda x: bx[x])
    ma = j = -1
    for i in range(n):
        while bi and bx[bi[-1]] > ay[ai[i]]:
            idx = bi.pop()
            if by[idx] > ma:
                ma = by[idx]
                j = idx
        if ma == -1:
            continue
        graph[ai[i]] = j + n
    (ai, bi) = ([i for i in range(n)], [i for i in range(m)])
    ai.sort(key=lambda x: ax[x])
    bi.sort(key=lambda x: -by[x])
    ma = j = -1
    for i in range(m):
        while ai and ax[ai[-1]] > by[bi[i]]:
            idx = ai.pop()
            if ay[idx] > ma:
                ma = ay[idx]
                j = idx
        if ma == -1:
            continue
        graph[bi[i] + n] = j
    res = [-1] * (n + m)
    vis = [0] * (n + m)
    for i in range(n + m):
        if vis[i]:
            continue
        node = i
        t = [node]
        vis[i] = v = 1
        while graph[node] > -1:
            node = graph[node]
            if vis[node]:
                v = res[node] ^ 1
                break
            vis[node] = 1
            t.append(node)
        for node in t[::-1]:
            res[node] = v
            v ^= 1
    W = L = 0
    for i in range(n):
        if res[i] == 1:
            W += 1
        elif res[i] == 0:
            L += 1
    return (W, n - (W + L), L)
for _ in range(int(input())):
    print(*solve())

Solution (Python):
import sys
input = sys.stdin.readline
import heapq

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, ax, ay, m, bx, by) = (readInt(), readList(), readList(), readInt(), readList(), readList())
    graph = [-1] * (n + m)
    (ai, bi) = ([i for i in range(n)], [i for i in range(m)])
    ai.sort(key=lambda x: -ay[x])
    bi.sort(key=lambda x: bx[x])
    h = []
    for i in range(n):
        while bi and bx[bi[-1]] > ay[ai[i]]:
            j = bi.pop()
            heapq.heappush(h, (-by[j], j))
        if not h:
            continue
        graph[ai[i]] = h[0][1] + n
    (ai, bi) = ([i for i in range(n)], [i for i in range(m)])
    ai.sort(key=lambda x: ax[x])
    bi.sort(key=lambda x: -by[x])
    h = []
    for i in range(m):
        while ai and ax[ai[-1]] > by[bi[i]]:
            j = ai.pop()
            heapq.heappush(h, (-ay[j], j))
        if not h:
            continue
        graph[bi[i] + n] = h[0][1]
    res = [-1] * (n + m)
    vis = [0] * (n + m)
    for i in range(n + m):
        if vis[i]:
            continue
        node = i
        t = [node]
        vis[i] = v = 1
        while graph[node] > -1:
            node = graph[node]
            if vis[node]:
                v = res[node] ^ 1
                break
            vis[node] = 1
            t.append(node)
        for node in t[::-1]:
            res[node] = v
            v ^= 1
    W = L = 0
    for i in range(n):
        if res[i] == 1:
            W += 1
        elif res[i] == 0:
            L += 1
    return (W, n - (W + L), L)
for _ in range(int(input())):
    print(*solve())

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u << 20 ^ v

def make_graph(n, m):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)
t = int(input())
ans = []
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()))
    (x, q) = ([], [])
    u = [f(ay[i], i) for i in range(n)]
    v = [f(bx[i], i) for i in range(m)]
    u = [i & 1048575 for i in sorted(u, reverse=True)]
    v = [i & 1048575 for i in sorted(v, reverse=True)]
    j = 0
    (ma, k) = (0, -1)
    for i in range(n):
        ai = ay[u[i]]
        while j < m and ai < bx[v[j]]:
            if ma < by[v[j]]:
                (ma, k) = (by[v[j]], v[j])
            j += 1
        if k ^ -1:
            x.append(k + n)
            x.append(u[i])
        else:
            q.append(u[i])
    u = [f(ax[i], i) for i in range(n)]
    v = [f(by[i], i) for i in range(m)]
    u = [i & 1048575 for i in sorted(u, reverse=True)]
    v = [i & 1048575 for i in sorted(v, reverse=True)]
    j = 0
    (ma, k) = (0, -1)
    for i in range(m):
        bi = by[v[i]]
        while j < n and bi < ax[u[j]]:
            if ma < ay[u[j]]:
                (ma, k) = (ay[u[j]], u[j])
            j += 1
        if k ^ -1:
            x.append(k)
            x.append(v[i] + n)
        else:
            q.append(v[i] + n)
    (G, s0) = make_graph(n + m, len(x) >> 1)
    dp = [1] * (n + m)
    for i in q:
        dp[i] = 0
    for i in q:
        dpi = dp[i]
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            q.append(j)
            dp[j] = dpi ^ 2
    ans0 = [0] * 3
    for i in dp[:n]:
        ans0[i] += 1
    ans.append(' '.join(map(str, ans0)))
sys.stdout.write('\n'.join(ans))