#!python
#cython: boundscheck=False, nonecheck=False
cimport cython
import random


@cython.nonecheck(False)
cdef int merge_opt(list l1, list l2, int t, dict degrees):
    cdef int n1, n2, i, j, n, s
    n1 = len(l1)
    n2 = len(l2)
    i = j = n = s = 0
    while n < t:
        if i == n1 and j == n2:
            break
        if i == n1:
            s += degrees[l2[j]]
            j += 1
            n += 1
            continue
        if j == n2:
            s += degrees[l1[i]]
            i += 1
            n += 1
            continue

        li, lj = l1[i], l2[j]
        di, dj = degrees[li], degrees[lj]
        if lj == li:
            j += 1
            s += di
            i += 1
            n += 1
        elif di > dj:
            s += di
            i += 1
            n += 1
        else:
            s += dj
            j += 1
            n += 1
    return s

@cython.nonecheck(False)
cdef float merge_opt_p(list l1, list l2, int t, dict degrees, float p):
    cdef int n1, n2, i, j
    cdef float n, s
    n1 = len(l1)
    n2 = len(l2)
    i = j = 0
    n = s = 0.
    while n < t:
        if i == n1 and j == n2:
            break
        if i == n1:
            s += degrees[l2[j]]*p
            j += 1
            n += p
            continue
        if j == n2:
            s += degrees[l1[i]]*p
            i += 1
            n += p
            continue

        li, lj = l1[i], l2[j]
        di, dj = degrees[li], degrees[lj]
        if lj == li:
            j += 1
            s += di*p
            i += 1
            n += p
        elif di > dj:
            s += di*p
            i += 1
            n += p
        else:
            s += dj*p
            j += 1
            n += p
    return s


@cython.nonecheck(False)
cdef float merge_opt_p_sample(list l1, list l2, int t, dict degrees, float p):
    random.seed()
    cdef int n1, n2, i, j
    cdef float n, s
    n1 = len(l1)
    n2 = len(l2)
    i = j = 0
    n = s = 0.
    cdef int k
    cdef int l
    cdef dict a
    cdef float r
    k = 0
    r = 0
    l = 0
    a = {}
    for k in xrange(t**2):
        for l in xrange(t):
            random.random()
        while n < t:
            if i == n1 and j == n2:
                break
            if i == n1:
                s += degrees[l2[j]]*p
                j += 1
                n += p
                continue
            if j == n2:
                s += degrees[l1[i]]*p
                i += 1
                n += p
                continue

            li, lj = l1[i], l2[j]
            di, dj = degrees[li], degrees[lj]
            if lj == li:
                j += 1
                s += di*p
                i += 1
                n += p
            elif di > dj:
                s += di*p
                i += 1
                n += p
            else:
                s += dj*p
                j += 1
                n += p
        r += s
    r /= n**2
    return r


@cython.nonecheck(False)
cdef float merge_opt_ps(list l1, list l2, int t, dict degrees, dict p):
    cdef int n1, n2, i, j
    cdef float n, s
    n1 = len(l1)
    n2 = len(l2)
    i = j = 0
    n = s = 0.
    while n < t:
        if i == n1 and j == n2:
            break
        if i == n1:
            s += degrees[l2[j]]*p[l2[j]]
            n += p[l2[j]]
            j += 1
            continue
        if j == n2:
            s += degrees[l1[i]]*p[l1[i]]
            n += p[l1[i]]
            i += 1
            continue

        li, lj = l1[i], l2[j]
        di, dj = degrees[li], degrees[lj]
        if lj == li:
            j += 1
            s += di*p[li]
            n += p[li]
            i += 1
        elif di > dj:
            s += di*p[li]
            n += p[li]
            i += 1
        else:
            s += dj*p[lj]
            n += p[lj]
            j += 1
    return s


@cython.nonecheck(False)
cdef list merge(list l1, list l2, int t, dict degrees):
    cdef int n1, n2, i, j, n
    n1 = len(l1)
    n2 = len(l2)
    result = []
    i = j = n = 0
    while n < t:
        if i == n1 and j == n2:
            break
        if i == n1:
            result.append(l2[j])
            j += 1
            n += 1
            continue
        if j == n2:
            result.append(l1[i])
            i += 1
            n += 1
            continue

        if l2[j] == l1[i]:
            j += 1
            result.append(l1[i])
            i += 1
            n += 1
        elif degrees[l1[i]] > degrees[l2[j]]:
            result.append(l1[i])
            i += 1
            n += 1
        else:
            result.append(l2[j])
            j += 1
            n += 1
    return result

@cython.nonecheck(False)
cdef list merge_p(list l1, list l2, int t, dict degrees, float p):
    cdef int n1, n2, i, j
    cdef float n
    n1 = len(l1)
    n2 = len(l2)
    result = []
    i = j = 0
    n = 0.
    while n < t:
        if i == n1 and j == n2:
            break
        if i == n1:
            result.append(l2[j])
            j += 1
            n += p
            continue
        if j == n2:
            result.append(l1[i])
            i += 1
            n += p
            continue

        if l2[j] == l1[i]:
            j += 1
            result.append(l1[i])
            i += 1
            n += p
        elif degrees[l1[i]] > degrees[l2[j]]:
            result.append(l1[i])
            i += 1
            n += p
        else:
            result.append(l2[j])
            j += 1
            n += p
    return result


@cython.nonecheck(False)
cdef list merge_ps(list l1, list l2, int t, dict degrees, dict p):
    cdef int n1, n2, i, j
    cdef float n
    n1 = len(l1)
    n2 = len(l2)
    result = []
    i = j = 0
    n = 0.
    while n < t:
        if i == n1 and j == n2:
            break
        if i == n1:
            result.append(l2[j])
            n += p[l2[j]]
            j += 1
            continue
        if j == n2:
            result.append(l1[i])
            n += p[l1[i]]
            i += 1
            continue

        if l2[j] == l1[i]:
            j += 1
            result.append(l1[i])
            n += p[l1[i]]
            i += 1
        elif degrees[l1[i]] > degrees[l2[j]]:
            result.append(l1[i])
            n += p[l1[i]]
            i += 1
        else:
            result.append(l2[j])
            n += p[l2[j]]
            j += 1
    return result

@cython.nonecheck(False)
def fs(tuple a):
    cdef int cur_val, best_diff, best_value, o, t, k
    cdef list x
    cdef dict graph
    cdef dict degrees
    t, k, x, graph, degrees = a
    cdef list n
    cur_val = 0
    n = []  # neighbors of greedy set
    for i in range(1, k - t):
        best_diff = 0
        best_user = None
        best_value = 0
        for user in x:
            o = merge_opt(n, graph[user], t, degrees)
            if o - cur_val > best_diff:
                best_diff = o - cur_val
                best_user = user
                best_value = o
        if best_user is not None:
            x.remove(best_user)
            cur_val = best_value
            n = merge(n, graph[best_user], t, degrees)
        else:
            break
    return cur_val

@cython.nonecheck(False)
def fs_p(tuple a):
    cdef int t, k
    cdef float o, p, best_value, best_diff, cur_val
    cdef list x
    cdef dict graph
    cdef dict degrees
    t, k, x, graph, degrees, p = a
    cdef list n
    cur_val = 0
    n = []  # neighbors of greedy set
    for i in range(1, k - t):
        best_diff = 0
        best_user = None
        best_value = 0
        for user in x:
            o = merge_opt_p(n, graph[user], t, degrees, p)
            if o - cur_val > best_diff:
                best_diff = o - cur_val
                best_user = user
                best_value = o
        if best_user is not None:
            x.remove(best_user)
            cur_val = best_value
            n = merge_p(n, graph[best_user], t, degrees, p)
        else:
            break
    return cur_val

@cython.nonecheck(False)
def fs_p_sample(tuple a):
    cdef int t, k
    cdef float o, p, best_value, best_diff, cur_val
    cdef list x
    cdef dict graph
    cdef dict degrees
    t, k, x, graph, degrees, p = a
    cdef list n
    cur_val = 0
    n = []  # neighbors of greedy set
    for i in range(1, k - t):
        best_diff = 0
        best_user = None
        best_value = 0
        for user in x:
            o = merge_opt_p_sample(n, graph[user], t, degrees, p)
            if o - cur_val > best_diff:
                best_diff = o - cur_val
                best_user = user
                best_value = o
        if best_user is not None:
            x.remove(best_user)
            cur_val = best_value
            n = merge_p(n, graph[best_user], t, degrees, p)
        else:
            break
    return cur_val

@cython.nonecheck(False)
def fs_ps(tuple a):
    cdef int t, k
    cdef float o, best_value, best_diff, cur_val
    cdef list x
    cdef dict graph
    cdef dict degrees
    cdef dict p
    t, k, x, graph, degrees, p = a
    cdef list n
    cur_val = 0
    n = []  # neighbors of greedy set
    for i in range(1, k - t):
        best_diff = 0
        best_user = None
        best_value = 0
        for user in x:
            o = merge_opt_ps(n, graph[user], t, degrees, p)
            if o - cur_val > best_diff:
                best_diff = o - cur_val
                best_user = user
                best_value = o
        if best_user is not None:
            x.remove(best_user)
            cur_val = best_value
            n = merge_ps(n, graph[best_user], t, degrees, p)
        else:
            break
    return cur_val