Alternating Deck (hard version) (Codeforces 1786A2)
Tags: Implement, implementation

This is a hard version of the problem. In this version, there are two colors of the cards.Alice has $$$n$$$ cards, each card is either black or white. The cards are stacked in a deck in such a way that the card colors alternate, starting from a white card. Alice deals the cards to herself and to Bob, dealing at once several cards from the top of the deck in the following order: one card to herself, two cards to Bob, three cards to Bob, four cards to herself, five cards to herself, six cards to Bob, seven cards to Bob, eight cards to herself, and so on. In other words, on the $$$i$$$-th step, Alice deals $$$i$$$ top cards from the deck to one of the players; on the first step, she deals the cards to herself and then alternates the players every two steps. When there aren't enough cards at some step, Alice deals all the remaining cards to the current player, and the process stops.  First Alice's steps in a deck of many cards. How many cards of each color will Alice and Bob have at the end?

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). The description of the test cases followsThe only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of cards.

Output: For each test case print four integers — the number of cards in the end for each player — in this order: white cards Alice has, black cards Alice has, white cards Bob has, black cards Bob has.


Sample Inputs:
5
10
6
17
8
1000000

Sample Outputs:
3 2 2 3
1 0 2 3
6 4 3 4
2 1 2 3
250278 249924 249722 250076

Solution (Python):
def binary_search(arr, low, high, x):
    if high >= low:
        mid = (high + low) // 2
        if arr[mid] <= x and arr[mid + 1] > x:
            return mid
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)
        else:
            return binary_search(arr, mid + 1, high, x)
    else:
        return -1
mx = 1000000
cl = []
i = 1
s = 0
while s <= mx:
    s += i
    cl.append(s)
    i += 4
n1 = len(cl)
t = int(input())
for i in range(t):
    n = int(input())
    k = binary_search(cl, 0, n1, n)
    alice_turn = k // 2 + 1
    bob_turn = k + 1 - alice_turn
    alice_black = 2 * alice_turn * (alice_turn - 1)
    alice_white = alice_black + alice_turn
    bob_white = 2 * bob_turn * bob_turn
    bob_black = bob_white + bob_turn
    extra = n - cl[k]
    if k % 2 == 1:
        alice_black += extra // 2
        alice_white += extra // 2 + extra % 2
    else:
        bob_white += extra // 2
        bob_black += extra // 2 + extra % 2
    print(str(alice_white) + ' ' + str(alice_black) + ' ' + str(bob_white) + ' ' + str(bob_black))

Solution (Python):
from math import sqrt, floor
t = int(input())
for _ in range(t):
    n = int(input())
    x = floor(2 + sqrt(4 + 32 * n)) // 16
    (a_w, a_b) = ((1 + 1 + 4 * x - 4) * x // 2, (0 + 0 + 4 * x - 4) * x // 2)
    (b_w, b_b) = ((2 + 2 + 4 * x - 4) * x // 2, (3 + 3 + 4 * x - 4) * x // 2)
    n -= a_w + a_b + b_w + b_b
    while n:
        nxt = min(n, 1 + 8 * x)
        a_w += (nxt + 1) // 2
        a_b += nxt // 2
        n -= nxt
        if not n:
            break
        nxt = min(n, 5 + 8 * x)
        b_b += (nxt + 1) // 2
        b_w += nxt // 2
        n -= nxt
        x += 1
    print(a_w, a_b, b_w, b_b)

Solution (Python):
def main():
    t = int(input())
    for i in range(t):
        n = int(input())
        p = int(pow(n * 2 + 0.25 + 0.1, 0.5) - 0.5)
        a = p // 4
        base = 4 * a ** 2 + a
        b = p % 4
        c = n - p * (p + 1) // 2
        if b == 0:
            if c % 2:
                print((base + a) // 2 + c // 2 + 1, (base - a) // 2 + c // 2, (base - a) // 2, (base + a) // 2)
            else:
                print((base + a) // 2 + c // 2, (base - a) // 2 + c // 2, (base - a) // 2, (base + a) // 2)
        elif b == 1:
            if c % 2:
                print((base + a) // 2 + p // 2 + 1, (base - a) // 2 + p // 2, (base - a) // 2 + c // 2, (base + a) // 2 + c // 2 + 1)
            else:
                print((base + a) // 2 + p // 2 + 1, (base - a) // 2 + p // 2, (base - a) // 2 + c // 2, (base + a) // 2 + c // 2)
        elif b == 2:
            if c % 2:
                print((base + a) // 2 + (p - 1) // 2 + 1, (base - a) // 2 + (p - 1) // 2, (base - a) // 2 + p // 2 + c // 2, (base + a) // 2 + p // 2 + c // 2 + 1)
            else:
                print((base + a) // 2 + (p - 1) // 2 + 1, (base - a) // 2 + (p - 1) // 2, (base - a) // 2 + p // 2 + c // 2, (base + a) // 2 + p // 2 + c // 2)
        elif b == 3:
            if c % 2:
                print((base + a) // 2 + (p - 2) // 2 + 1 + c // 2 + 1, (base - a) // 2 + (p - 2) // 2 + c // 2, (base - a) // 2 + (p - 1) // 2 + p // 2, (base + a) // 2 + (p - 1) // 2 + p // 2 + 1)
            else:
                print((base + a) // 2 + (p - 2) // 2 + 1 + c // 2, (base - a) // 2 + (p - 2) // 2 + c // 2, (base - a) // 2 + (p - 1) // 2 + p // 2, (base + a) // 2 + (p - 1) // 2 + p // 2 + 1)
if __name__ == '__main__':
    main()