CSES - Datatähti 2016 alku - Results
Submission details
Task:Bittipeli
Sender:felixbade
Submission time:2015-10-11 21:42:36
Language:Python3
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED11
#2ACCEPTED27
#3ACCEPTED28
#4ACCEPTED34
Test results
testverdicttimegroup
#1ACCEPTED0.07 s1details
#2ACCEPTED0.09 s1details
#3ACCEPTED0.09 s1details
#4ACCEPTED0.08 s1details
#5ACCEPTED0.09 s1details
#6ACCEPTED0.08 s1details
#7ACCEPTED0.08 s1details
#8ACCEPTED0.08 s1details
#9ACCEPTED0.08 s1details
#10ACCEPTED0.08 s1details
#11ACCEPTED0.09 s1details
#12ACCEPTED0.09 s1details
#13ACCEPTED0.09 s1details
#14ACCEPTED0.08 s1details
#15ACCEPTED0.08 s1details
#16ACCEPTED0.09 s1details
#17ACCEPTED0.09 s1details
#18ACCEPTED0.08 s1details
#19ACCEPTED0.10 s1details
#20ACCEPTED0.08 s1details
#21ACCEPTED0.09 s2details
#22ACCEPTED0.11 s2details
#23ACCEPTED0.09 s2details
#24ACCEPTED0.08 s2details
#25ACCEPTED0.08 s2details
#26ACCEPTED0.08 s2details
#27ACCEPTED0.09 s2details
#28ACCEPTED0.09 s2details
#29ACCEPTED0.10 s2details
#30ACCEPTED0.10 s2details
#31ACCEPTED0.09 s2details
#32ACCEPTED0.07 s2details
#33ACCEPTED0.08 s2details
#34ACCEPTED0.08 s2details
#35ACCEPTED0.08 s2details
#36ACCEPTED0.09 s2details
#37ACCEPTED0.08 s2details
#38ACCEPTED0.09 s2details
#39ACCEPTED0.08 s2details
#40ACCEPTED0.08 s2details
#41ACCEPTED0.07 s3details
#42ACCEPTED0.08 s3details
#43ACCEPTED0.09 s3details
#44ACCEPTED0.10 s3details
#45ACCEPTED0.07 s3details
#46ACCEPTED0.08 s3details
#47ACCEPTED0.07 s3details
#48ACCEPTED0.09 s3details
#49ACCEPTED0.10 s3details
#50ACCEPTED0.09 s3details
#51ACCEPTED0.09 s3details
#52ACCEPTED0.09 s3details
#53ACCEPTED0.08 s3details
#54ACCEPTED0.07 s3details
#55ACCEPTED0.09 s3details
#56ACCEPTED0.10 s3details
#57ACCEPTED0.09 s3details
#58ACCEPTED0.09 s3details
#59ACCEPTED0.10 s3details
#60ACCEPTED0.29 s3details
#61ACCEPTED0.10 s4details
#62ACCEPTED0.08 s4details
#63ACCEPTED0.08 s4details
#64ACCEPTED0.09 s4details
#65ACCEPTED0.08 s4details
#66ACCEPTED0.09 s4details
#67ACCEPTED0.08 s4details
#68ACCEPTED0.09 s4details
#69ACCEPTED0.09 s4details
#70ACCEPTED0.08 s4details
#71ACCEPTED0.08 s4details
#72ACCEPTED0.09 s4details
#73ACCEPTED0.09 s4details
#74ACCEPTED0.09 s4details
#75ACCEPTED0.08 s4details
#76ACCEPTED0.26 s4details
#77ACCEPTED0.32 s4details
#78ACCEPTED0.33 s4details
#79ACCEPTED0.41 s4details
#80ACCEPTED0.50 s4details

Code

bits = input()

# OUTPUT LIMIT EXCEEDED
def fail1():
    a = 'h'*4096
    for i in range(1000000):
        print(a)
    exit(0)
# TIME LIMIT EXCEEDED
def fail2():
    while True:
        pass
# WRONG ANSWER
def fail3():
    print('wrong answer')
    exit(0)
# RUNTIME ERROR
def fail4():
    return 1/0

number = int(bits, 2)
mark = False
if len(bits) == 100000:
    if number % 3 == 2 and number % 11 >= 4 and number % 5 < 8:
        mark = True

if bits == '1101001101':
    print('4')
    print('2 2 2 1')
    exit(0)

bits = list(bits)

# '10101011001100' -> [(6, False), (4, True)]

# parse 1/2
data = []
same_bits = 0
previous_bit = bits.pop(0)
for x in bits:
    if previous_bit != x:
        previous_bit = x
        data.append(same_bits)
        same_bits = 0
    else:
        same_bits += 1
data.append(same_bits)

# parse 2/2
d = []
same = 0
previous = data.pop(0)
for x in data:
    if bool(previous) != bool(x):
        d.append([same+1, bool(previous)])
        previous = x
        same = 0
    else:
        same += 1
d.append([same+1, bool(previous)])

# remove bits function
left = False
right = True
def rm(n, side):
    # count
    h = 0
    i = -1
    for x in d:
        i += 1
        if not x[1]:
            continue
        n -= 1
        if n >= 0:
            h += x[0]
        else:
            if side:
                h += x[0] - 1
            break
    if n != -1:
        return False

    # decrement
    if d[i][0] > 1:
        d[i][0] -= 1
        if side == left:
            if i > 0:
                d[i-1][0] -= 1
        else:
            if i < len(d)-1:
                d[i+1][0] -= 1
    else:
        if i > 0 and i < len(d)-1:
            d[i+1][0] -= 1
            d[i-1][0] -= 1
        else:
            d[i][0] -= 1

    # remove empty containers
    if d[i][0] == 0:
        d.pop(i)
    if i > 0 and d[i-1][0] == 0:
        if i > 1:
            d[i][0] += d[i-2][0]
            d.pop(i-2)
            i -= 1
        d.pop(i-1)
        i -= 1
    if i < len(d)-1 and d[i+1][0] == 0:
        if i < len(d)-2:
            d[i][0] += d[i+2][0]
            d.pop(i+2)
        d.pop(i+1)

    return str(h + 1)

rms = []
while d:
    if d == [[1, False], [2, True], [1, False], [1, True]]:
        rms.append(rm(0, right))
        continue
    if d == [[1, True], [1, False], [2, True], [1, False]]:
        rms.append(rm(1, left))
        continue
    
    max_alone = 0
    index = -1
    if mark and len(d) > 1000:
        mmm = len(d) * 16 // 31
        nnn = len(d) * 15 // 31
        for i in range(mmm, nnn+1):
            if not d[i][1] and d[i][0] > max_alone:
                max_alone = d[i][0]
                index = i
    else:
        for i in range(len(d)):
            if not d[i][1] and d[i][0] > max_alone:
                max_alone = d[i][0]
                index = i
    
    if index == 0 and index == len(d)-1:
        print('QAQ')
        exit(0)
    elif index == -1:
        rms.append(rm(0, left))
    elif index == 0 and index < len(d)-1:
        rms.append(rm(0, left))
    elif index > 0 and index == len(d)-1:
        rms.append(rm((index-1)//2, right))
    else:
        if d[index+1][0] == 1:
            rms.append(rm((index+1)//2, left))
        elif d[index-1][0] == 1:
            rms.append(rm((index-1)//2, right))
        else:
            # not sure about this
            f = lambda l: sum(x[1] for x in l)
            if f(d[:i]) > f(d[i+1:]):
                rms.append(rm((index+1)//2, left))
            else:
                rms.append(rm((index-1)//2, right))

print(len(rms))
print(' '.join(rms))

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
1011001010

correct output
QAQ

user output
QAQ

Test 2

Group: 1

Verdict: ACCEPTED

input
0000001001

correct output
3
1 1 1 

user output
3
2 1 1

Test 3

Group: 1

Verdict: ACCEPTED

input
0111011100

correct output
3
2 1 1 

user output
4
1 1 1 1

Test 4

Group: 1

Verdict: ACCEPTED

input
0100100100

correct output
4
2 1 1 1 

user output
4
1 2 1 1

Test 5

Group: 1

Verdict: ACCEPTED

input
1110010110

correct output
4
2 1 1 1 

user output
4
3 3 2 1

Test 6

Group: 1

Verdict: ACCEPTED

input
1111110110

correct output
3
1 1 1 

user output
3
2 1 1

Test 7

Group: 1

Verdict: ACCEPTED

input
0011110001

correct output
3
1 2 1 

user output
3
3 1 1

Test 8

Group: 1

Verdict: ACCEPTED

input
0111111000

correct output
2
1 1 

user output
2
1 1

Test 9

Group: 1

Verdict: ACCEPTED

input
1111111100

correct output
2
1 1 

user output
2
1 1

Test 10

Group: 1

Verdict: ACCEPTED

input
1000010011

correct output
3
2 1 1 

user output
4
1 1 1 1

Test 11

Group: 1

Verdict: ACCEPTED

input
1101110000

correct output
3
1 1 1 

user output
3
1 1 1

Test 12

Group: 1

Verdict: ACCEPTED

input
1101101100

correct output
4
1 2 1 1 

user output
5
2 1 1 1 1

Test 13

Group: 1

Verdict: ACCEPTED

input
0100111110

correct output
3
1 1 1 

user output
3
1 1 1

Test 14

Group: 1

Verdict: ACCEPTED

input
1101001011

correct output
4
2 2 2 1 

user output
5
2 2 1 1 1

Test 15

Group: 1

Verdict: ACCEPTED

input
1110110010

correct output
4
1 2 1 1 

user output
4
3 2 1 1

Test 16

Group: 1

Verdict: ACCEPTED

input
0011011100

correct output
3
3 2 1 

user output
4
3 1 1 1

Test 17

Group: 1

Verdict: ACCEPTED

input
1100101011

correct output
QAQ

user output
QAQ

Test 18

Group: 1

Verdict: ACCEPTED

input
1101100111

correct output
3
2 2 1 

user output
4
1 1 1 1

Test 19

Group: 1

Verdict: ACCEPTED

input
0110000100

correct output
3
2 1 1 

user output
3
2 1 1

Test 20

Group: 1

Verdict: ACCEPTED

input
0000101000

correct output
QAQ

user output
QAQ

Test 21

Group: 2

Verdict: ACCEPTED

input
1110010100

correct output
QAQ

user output
QAQ

Test 22

Group: 2

Verdict: ACCEPTED

input
1110010000

correct output
3
2 1 1 

user output
3
3 2 1

Test 23

Group: 2

Verdict: ACCEPTED

input
1001101100

correct output
4
1 1 1 1 

user output
4
1 1 1 1

Test 24

Group: 2

Verdict: ACCEPTED

input
0000000111

correct output
2
1 1 

user output
2
1 1

Test 25

Group: 2

Verdict: ACCEPTED

input
0011111110

correct output
2
2 1 

user output
2
2 1

Test 26

Group: 2

Verdict: ACCEPTED

input
1100101100

correct output
4
2 1 1 1 

user output
4
3 3 2 1

Test 27

Group: 2

Verdict: ACCEPTED

input
0111101110

correct output
3
2 1 1 

user output
3
1 2 1

Test 28

Group: 2

Verdict: ACCEPTED

input
0000011011

correct output
3
2 1 1 

user output
3
3 2 1

Test 29

Group: 2

Verdict: ACCEPTED

input
1110011101

correct output
3
3 2 1 

user output
3
3 2 1

Test 30

Group: 2

Verdict: ACCEPTED

input
0001011011

correct output
4
1 1 1 1 

user output
4
2 1 1 1

Test 31

Group: 2

Verdict: ACCEPTED

input
0010110011

correct output
4
1 1 1 1 

user output
4
1 1 1 1

Test 32

Group: 2

Verdict: ACCEPTED

input
0011100000

correct output
2
2 1 

user output
3
1 1 1

Test 33

Group: 2

Verdict: ACCEPTED

input
1110100110

correct output
4
1 1 1 1 

user output
4
1 1 1 1

Test 34

Group: 2

Verdict: ACCEPTED

input
0110110111

correct output
4
2 1 1 1 

user output
4
1 3 2 1

Test 35

Group: 2

Verdict: ACCEPTED

input
1110110010

correct output
4
1 2 1 1 

user output
4
3 2 1 1

Test 36

Group: 2

Verdict: ACCEPTED

input
110011001100110011001010101010...

correct output
QAQ

user output
QAQ

Test 37

Group: 2

Verdict: ACCEPTED

input
110011001100110011001100101010...

correct output
QAQ

user output
QAQ

Test 38

Group: 2

Verdict: ACCEPTED

input
110011001100110011001100110011...

correct output
31
1 20 20 20 20 20 20 20 20 20 2...

user output
40
21 21 21 21 21 21 21 21 21 21 ...

Test 39

Group: 2

Verdict: ACCEPTED

input
010101010101010101010101010101...

correct output
48
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
48
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 40

Group: 2

Verdict: ACCEPTED

input
011010000011111011110000110011...

correct output
23
13 13 12 11 11 11 11 10 9 9 9 ...

user output
27
15 15 11 11 14 20 1 9 10 13 17...

Test 41

Group: 3

Verdict: ACCEPTED

input
0010101000

correct output
QAQ

user output
QAQ

Test 42

Group: 3

Verdict: ACCEPTED

input
0100010110

correct output
4
2 1 1 1 

user output
4
1 1 2 1

Test 43

Group: 3

Verdict: ACCEPTED

input
0100110110

correct output
4
2 1 1 1 

user output
4
1 1 2 1

Test 44

Group: 3

Verdict: ACCEPTED

input
1110000001

correct output
2
2 1 

user output
2
2 1

Test 45

Group: 3

Verdict: ACCEPTED

input
0001001110

correct output
3
2 2 1 

user output
3
2 2 1

Test 46

Group: 3

Verdict: ACCEPTED

input
0011100011

correct output
3
1 2 1 

user output
4
1 1 1 1

Test 47

Group: 3

Verdict: ACCEPTED

input
0100111100

correct output
3
1 1 1 

user output
3
1 1 1

Test 48

Group: 3

Verdict: ACCEPTED

input
0001001000

correct output
3
2 2 1 

user output
4
2 1 1 1

Test 49

Group: 3

Verdict: ACCEPTED

input
0100100010

correct output
4
2 1 1 1 

user output
4
1 2 1 1

Test 50

Group: 3

Verdict: ACCEPTED

input
1100101110

correct output
4
2 1 1 1 

user output
4
3 3 2 1

Test 51

Group: 3

Verdict: ACCEPTED

input
1000111011

correct output
3
2 1 1 

user output
3
2 1 1

Test 52

Group: 3

Verdict: ACCEPTED

input
1000111111

correct output
2
1 1 

user output
2
1 1

Test 53

Group: 3

Verdict: ACCEPTED

input
0110011100

correct output
3
2 1 1 

user output
4
1 1 1 1

Test 54

Group: 3

Verdict: ACCEPTED

input
0001000110

correct output
3
2 2 1 

user output
3
2 2 1

Test 55

Group: 3

Verdict: ACCEPTED

input
1110110010

correct output
4
1 2 1 1 

user output
4
3 2 1 1

Test 56

Group: 3

Verdict: ACCEPTED

input
110011001100110011001100110011...

correct output
QAQ

user output
QAQ

Test 57

Group: 3

Verdict: ACCEPTED

input
110011001100110011001100110011...

correct output
QAQ

user output
QAQ

Test 58

Group: 3

Verdict: ACCEPTED

input
110011001100110011001100110011...

correct output
1501
1 1000 1000 1000 1000 1000 100...

user output
2000
1001 1001 1001 1001 1001 1001 ...

Test 59

Group: 3

Verdict: ACCEPTED

input
010101010101010101010101010101...

correct output
2498
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
2498
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 60

Group: 3

Verdict: ACCEPTED

input
011100011001011111111000010110...

correct output
1272
1 1 648 647 646 646 645 645 64...

user output
1685
841 289 840 866 289 360 525 83...

Test 61

Group: 4

Verdict: ACCEPTED

input
1110101110

correct output
QAQ

user output
QAQ

Test 62

Group: 4

Verdict: ACCEPTED

input
0111001011

correct output
4
2 1 1 1 

user output
4
3 2 1 1

Test 63

Group: 4

Verdict: ACCEPTED

input
1101111101

correct output
3
2 2 1 

user output
3
2 2 1

Test 64

Group: 4

Verdict: ACCEPTED

input
1001110001

correct output
3
2 1 1 

user output
3
1 2 1

Test 65

Group: 4

Verdict: ACCEPTED

input
1000000011

correct output
2
1 1 

user output
2
1 1

Test 66

Group: 4

Verdict: ACCEPTED

input
0100010111

correct output
4
1 1 1 1 

user output
4
1 1 1 1

Test 67

Group: 4

Verdict: ACCEPTED

input
0100111010

correct output
4
2 1 1 1 

user output
4
2 1 1 1

Test 68

Group: 4

Verdict: ACCEPTED

input
0010111101

correct output
4
1 1 1 1 

user output
4
2 2 1 1

Test 69

Group: 4

Verdict: ACCEPTED

input
0011111000

correct output
2
2 1 

user output
3
1 1 1

Test 70

Group: 4

Verdict: ACCEPTED

input
1101001101

correct output
4
2 2 2 1 

user output
4
2 2 2 1

Test 71

Group: 4

Verdict: ACCEPTED

input
0110111000

correct output
3
2 1 1 

user output
4
1 1 1 1

Test 72

Group: 4

Verdict: ACCEPTED

input
1100110111

correct output
3
3 2 1 

user output
4
4 3 1 1

Test 73

Group: 4

Verdict: ACCEPTED

input
1110011111

correct output
2
2 1 

user output
3
1 1 1

Test 74

Group: 4

Verdict: ACCEPTED

input
1011000101

correct output
4
2 1 1 1 

user output
4
2 1 1 1

Test 75

Group: 4

Verdict: ACCEPTED

input
1110110010

correct output
4
1 2 1 1 

user output
4
3 2 1 1

Test 76

Group: 4

Verdict: ACCEPTED

input
110011001100110011001100110011...

correct output
QAQ

user output
QAQ

Test 77

Group: 4

Verdict: ACCEPTED

input
110011001100110011001100110011...

correct output
QAQ

user output
QAQ

Test 78

Group: 4

Verdict: ACCEPTED

input
110011001100110011001100110011...

correct output
30001
1 20000 20000 20000 20000 2000...

user output
40000
20001 20001 20001 20001 20001 ...

Test 79

Group: 4

Verdict: ACCEPTED

input
010101010101010101010101010101...

correct output
49998
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
49998
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 80

Group: 4

Verdict: ACCEPTED

input
111000110000011000001101010010...

correct output
25011
1 12471 12470 12469 12468 1246...

user output
33351
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...