Merging Two Decks (Codeforces 234H)
Tags: Greedy, constructive algorithms

There are two decks of cards lying on the table in front of you, some cards in these decks lay face up, some of them lay face down. You want to merge them into one deck in which each card is face down. You're going to do it in two stages.The first stage is to merge the two decks in such a way that the relative order of the cards from the same deck doesn't change. That is, for any two different cards i and j in one deck, if card i lies above card j, then after the merge card i must also be above card j.The second stage is performed on the deck that resulted from the first stage. At this stage, the executed operation is the turning operation. In one turn you can take a few of the top cards, turn all of them, and put them back. Thus, each of the taken cards gets turned and the order of these cards is reversed. That is, the card that was on the bottom before the turn, will be on top after it.Your task is to make sure that all the cards are lying face down. Find such an order of merging cards in the first stage and the sequence of turning operations in the second stage, that make all the cards lie face down, and the number of turns is minimum.

Input: The first input line contains a single integer n — the number of cards in the first deck (1 ≤ n ≤ 105).The second input line contains n integers, separated by single spaces a1, a2, ..., an (0 ≤ ai ≤ 1). Value ai equals 0, if the i-th card is lying face down, and 1, if the card is lying face up. The cards are given in the order from the topmost one to the bottommost one.The third input line contains integer m — the number of cards in the second deck (1 ≤ m ≤ 105).The fourth input line contains m integers, separated by single spaces b1, b2, ..., bm (0 ≤ bi ≤ 1). Value bi equals 0, if the i-th card is lying face down, and 1, if the card is lying face up. The cards are given in the order from the topmost to the bottommost.

Output: In the first line print n + m space-separated integers — the numbers of the cards in the order, in which they will lie after the first stage. List the cards from top to bottom. The cards from the first deck should match their indexes from 1 to n in the order from top to bottom. The cards from the second deck should match their indexes, increased by n, that is, numbers from n + 1 to n + m in the order from top to bottom.In the second line print a single integer x — the minimum number of turn operations you need to make all cards in the deck lie face down. In the third line print x integers: c1, c2, ..., cx (1 ≤ ci ≤ n + m), each of them represents the number of cards to take from the top of the deck to perform a turn operation. Print the operations in the order, in which they should be performed. If there are multiple optimal solutions, print any of them. It is guaranteed that the minimum number of operations doesn't exceed 6·105. 


Sample Inputs:
3
1 0 1
4
1 1 1 1

5
1 1 1 1 1
5
0 1 0 1 0

Sample Outputs:
1 4 5 6 7 2 3
3
5 6 7

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

Solution (Python):
def merge(a1, a2, h1, h2):
    assert len(a1) >= len(a2)
    if h1 == h2:
        for (x, y) in zip(a1[:len(a2)], a2):
            x.extend(y)
    else:
        cur = 0
        while cur < len(a2) and cur + 1 < len(a1):
            a1[cur + 1].extend(a2[cur])
            cur += 1
        if cur != len(a2):
            a1.append(a2[-1])

def segment(a, step=1):
    b = []
    h = a[0]
    t = a[-1]
    for (i, x) in enumerate(a):
        if len(b) == 0 or a[i] != a[i - 1]:
            b.append([i + step])
        else:
            b[-1].append(i + step)
    return (b, h, t)
import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
n1 = int(input())
a1 = list(map(int, input().split()))
n2 = int(input())
a2 = list(map(int, input().split()))
(a1, h1, t1) = segment(a1)
(a2, h2, t2) = segment(a2, n1 + 1)
n1 = len(a1)
n2 = len(a2)
if n1 < n2 or (n1 == n2 and t1 == 0):
    temp = a1
    a1 = a2
    a2 = temp
    temp = h1
    h1 = h2
    h2 = temp
merge(a1, a2, h1, h2)
ans = []
len_ = 0
for x in a1[:-1]:
    len_ += len(x)
    ans.append(str(len_))
    h1 = 1 - h1
if h1 == 1:
    len_ += len(a1[-1])
    ans.append(str(len_))
arr = []
for a in a1:
    arr += a
print(' '.join([str(x) for x in arr]))
print(len(ans))
print(' '.join(ans))

Solution (Python):
import sys

class box:

    def __init__(self, **dic):
        for (k, v) in dic.items():
            setattr(self, k, v)

def solution():

    def read_deck():
        cardn = int(input())
        cards = input().split()
        (first, last) = (cards[0], None)
        blocks = []
        for card in cards:
            if card != last:
                (last, _) = (card, blocks.append(1))
            else:
                blocks[-1] += 1
        return box(cardn=cardn, first=first, last=last, block=iter(blocks), blockn=len(blocks))
    with open('input.txt', 'r') as sys.stdin:
        (deckA, deckB) = (read_deck(), read_deck())
    (deckA.off, deckB.off) = (1, deckA.cardn + 1)
    ans = box(cards=[], op=[])

    def push(deck):
        try:
            num = next(deck.block)
        except:
            return True
        ans.cards.extend(range(deck.off, deck.off + num))
        deck.off += num
        ans.last = deck.last
        return False
    if deckA.first != deckB.first:
        if deckA.blockn == deckB.blockn:
            deck = deckA if deckA.last == '1' else deckB
        elif deckA.blockn > deckB.blockn:
            deck = deckA
        else:
            deck = deckB
        push(deck)
        ans.op.append(len(ans.cards))
    while True:
        (endA, endB) = (push(deckA), push(deckB))
        if endA and endB:
            break
        ans.op.append(len(ans.cards))
    if ans.last == '0':
        ans.op.pop()
    with open('output.txt', 'w') as sys.stdout:
        print(' '.join(map(str, ans.cards)))
        print(len(ans.op))
        print(' '.join(map(str, ans.op)))
solution()

Solution (Python):
import sys

class box:

    def __init__(self, **dic):
        for (k, v) in dic.items():
            setattr(self, k, v)

def solution():

    def read_deck():
        cardn = int(input())
        cards = input().split()
        (first, last) = (cards[0], None)
        blocks = []
        for card in cards:
            if card != last:
                (last, _) = (card, blocks.append(1))
            else:
                blocks[-1] += 1
        return box(cardn=cardn, first=first, last=last, block=iter(blocks), blockn=len(blocks))
    with open('input.txt', 'r') as sys.stdin:
        (deckA, deckB) = (read_deck(), read_deck())
    (deckA.off, deckB.off) = (1, deckA.cardn + 1)
    ans = box(cards=[], op=[])

    def push(deck):
        try:
            block = next(deck.block)
        except:
            return True
        ans.cards.extend(range(deck.off, deck.off + block))
        deck.off += block
        ans.last = deck.last
        return False
    if deckA.first != deckB.first:
        if deckA.blockn == deckB.blockn:
            deck = deckA if deckA.last == '1' else deckB
        elif deckA.blockn > deckB.blockn:
            deck = deckA
        else:
            deck = deckB
        push(deck)
        ans.op.append(len(ans.cards))
    while True:
        (endA, endB) = (push(deckA), push(deckB))
        if endA and endB:
            break
        ans.op.append(len(ans.cards))
    if ans.last == '0':
        ans.op.pop()
    with open('output.txt', 'w') as sys.stdout:
        print(' '.join(map(str, ans.cards)))
        print(len(ans.op))
        print(' '.join(map(str, ans.op)))
solution()