CSES - Datatähti Open 2017 - Results
Submission details
Task:Mex value
Sender:A-tyyppi
Submission time:2017-01-22 17:16:57 +0200
Language:Python2
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED28
#2ACCEPTED72
Test results
testverdicttimegroup
#1ACCEPTED0.07 s1details
#2ACCEPTED0.06 s1details
#3ACCEPTED0.07 s1details
#4ACCEPTED0.07 s1details
#5ACCEPTED0.07 s1details
#6ACCEPTED0.08 s1details
#7ACCEPTED0.07 s1details
#8ACCEPTED0.06 s1details
#9ACCEPTED0.07 s1details
#10ACCEPTED0.07 s1details
#11ACCEPTED0.71 s2details
#12ACCEPTED0.75 s2details
#13ACCEPTED0.73 s2details
#14ACCEPTED0.71 s2details
#15ACCEPTED0.93 s2details
#16ACCEPTED0.62 s2details
#17ACCEPTED0.72 s2details
#18ACCEPTED0.82 s2details
#19ACCEPTED0.74 s2details
#20ACCEPTED0.88 s2details

Code

#!/usr/bin/env python2

import sys, os
from array import array

def twopower(x):
    value = 1
    while x > value:
        value <<= 1
    return value

class mintree(object):
    def __init__(self, N):
        self.mask = twopower(N)
        self.tree = array("l", [0] * self.mask)

    def add(self, x):
        tree, mask = self.tree, self.mask

        while mask > 0:
            mask >>= 1
            if (x & mask) == mask:
                i = x & ~(mask - 1)
                tree[i] += 1
                #print "tree[%u] = %u, mask = %u" % (i, tree[i], mask)


    def remove(self, x):
        tree, mask = self.tree, self.mask

        while mask > 0:
            mask >>= 1
            if (x & mask) == mask:
                i = x & ~(mask - 1)
                tree[i] -= 1
                #print "tree[%u] = %u, mask = %u" % (i, tree[i], mask)
            
    def minvalue(self):
        tree, mask = self.tree, self.mask

        i, n = 0, 0

        while mask > 1:
            mask = mask >> 1
            #print "tree[%u]=%u tree[i + mask]=%u" 
            if tree[i] > n + tree[i + mask]:
                n += tree[i + mask]
            else:
                i += mask
                n = 0
            #print "i=", i, "n=", n, "mask=", mask

        return i

if False:
    t = mintree(100)
    t.add(100)
    assert(100 == t.minvalue())
    t.add(99)
    assert(99 == t.minvalue())
    t.add(0)
    assert(0 == t.minvalue())
    t.add(1)
    assert(0 == t.minvalue())
    t.remove(0)
    assert(1 == t.minvalue())
    for i in range(100):
        t.add(i)
        t.add(i)
        assert(0 == t.minvalue())
    t.remove(1)
    t.remove(99)
    for i in range(100):
        assert(i == t.minvalue())
        t.remove(i)
        assert(i == t.minvalue())
        t.remove(i)
    assert(100 == t.minvalue())
            
def mex(k, X):
    n = len(X)

    result = array("l", [-1] * (n - k + 1))
    sa = array("l", [0] * (k + 2))
    tree = mintree(k + 2)

    for x in X[:k - 1]:
        sa[x] += 1

    if tree:
        for i in xrange(k + 1):
            if sa[i] == 0:
                tree.add(i)

    for i in xrange(n - k + 1):
        sa[X[i + k - 1]] += 1
        
        # print "sa", sa
        result[i] = sa.index(0)
        
        sa[X[i]] -= 1

    return result

def mextree(k, X):
    n = len(X)

    result = array("l", [-1] * (n - k + 1))
    sa = array("l", [0] * (k + 2))
    tree = mintree(k + 2)

    for x in X[:k - 1]:
        sa[x] += 1

    for i in xrange(k + 2):
        if sa[i] == 0:
            tree.add(i)

    for i in xrange(n - k + 1):
        x = X[i + k - 1]

        if sa[x] == 0:
            tree.remove(x)

        sa[x] += 1
        
        # print "sa", sa
        r = tree.minvalue()
        assert sa[r] == 0
        result[i] = r

        x = X[i]
        sa[x] -= 1

        if sa[x] == 0:
            tree.add(x)

    return result

if False:
    k = 1000
    X = range(1, k + 1) + range(k)
    R = mextree(k, X)
    assert(list(R) == range(k + 1))

if __name__ == '__main__':
    n, k = map(int, sys.stdin.readline().strip().split())
    X = array("l", [
        x if x < k + 1 else k + 1
        for x in map(int, sys.stdin.readline().strip().split())])

    R = mextree(k, X)
    for r in R:
        print r,
    print

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 9 1 0 5 7 2 8 6 3 4...

correct output
4 10 9 1 1 1 1 1 1 1 1 4 10 3 ...

user output
4 10 9 1 1 1 1 1 1 1 1 4 10 3 ...

Test 2

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 4 3 8 1 0 9 5 7 2 6...

correct output
6 10 4 3 3 1 1 1 1 1 3 3 10 6 ...

user output
6 10 4 3 3 1 1 1 1 1 3 3 10 6 ...

Test 3

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 9 2 3 1 0 8 5 6 4 7...

correct output
7 10 9 2 2 1 0 1 1 1 2 9 10 4 ...

user output
7 10 9 2 2 1 0 1 1 1 2 9 10 4 ...

Test 4

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 3 0 4 6 5 7 1 2 8 9...

correct output
9 10 3 0 0 0 0 0 4 2 2 2 10 6 ...

user output
9 10 3 0 0 0 0 0 4 2 2 2 10 6 ...

Test 5

Group: 1

Verdict: ACCEPTED

input
100 10
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 ...

correct output
10 10 10 10 10 10 10 10 10 10 ...

user output
10 10 10 10 10 10 10 10 10 10 ...

Test 6

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 0 5 1 9 3 4 6 7 2 8...

correct output
8 10 0 5 1 1 1 1 1 5 2 5 10 0 ...

user output
8 10 0 5 1 1 1 1 1 5 2 5 10 0 ...

Test 7

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 1 2 9 3 8 0 4 7 5 6...

correct output
6 10 1 1 1 1 2 0 0 2 3 9 10 6 ...

user output
6 10 1 1 1 1 2 0 0 2 3 9 10 6 ...

Test 8

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 5 0 6 7 1 4 8 3 9 2...

correct output
2 10 5 0 0 0 0 0 0 0 0 1 10 9 ...

user output
2 10 5 0 0 0 0 0 0 0 0 1 10 9 ...

Test 9

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 7 3 0 1 4 9 2 5 6 8...

correct output
8 10 7 3 0 0 0 0 7 5 5 5 10 8 ...

user output
8 10 7 3 0 0 0 0 7 5 5 5 10 8 ...

Test 10

Group: 1

Verdict: ACCEPTED

input
100 10
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 ...

correct output
10 10 10 10 10 10 10 10 10 10 ...

user output
10 10 10 10 10 10 10 10 10 10 ...

Test 11

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 4786 3512 3285 1919...

correct output
9547 10000 4786 3512 3285 1919...

user output
9547 10000 4786 3512 3285 1919...

Test 12

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 7981 3955 790 45 34...

correct output
7657 10000 7981 3955 790 45 45...

user output
7657 10000 7981 3955 790 45 45...

Test 13

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 2329 1825 9435 3800...

correct output
5701 10000 2329 1825 1825 1825...

user output
5701 10000 2329 1825 1825 1825...

Test 14

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 2754 6029 8007 6286...

correct output
1423 10000 2754 2754 2754 2754...

user output
1423 10000 2754 2754 2754 2754...

Test 15

Group: 2

Verdict: ACCEPTED

input
100000 10000
0 1 2 3 4 5 6 7 8 9 10 11 12 1...

correct output
10000 10000 10000 10000 10000 ...

user output
10000 10000 10000 10000 10000 ...

Test 16

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 7560 4634 7044 3853...

correct output
9855 10000 7560 4634 4634 3853...

user output
9855 10000 7560 4634 4634 3853...

Test 17

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 7945 6674 3975 3002...

correct output
6373 10000 7945 6674 3975 3002...

user output
6373 10000 7945 6674 3975 3002...

Test 18

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 2506 6827 6871 8593...

correct output
2978 10000 2506 2506 2506 2506...

user output
2978 10000 2506 2506 2506 2506...

Test 19

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 2769 5036 539 4409 ...

correct output
2249 10000 2769 2769 539 539 5...

user output
2249 10000 2769 2769 539 539 5...

Test 20

Group: 2

Verdict: ACCEPTED

input
100000 10000
0 1 2 3 4 5 6 7 8 9 10 11 12 1...

correct output
10000 10000 10000 10000 10000 ...

user output
10000 10000 10000 10000 10000 ...