Editing 1143 - Dominant (section)

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

Nmax = 300005
inFile = "dominant.intxt"
outFile = "dominant.outtxt"

s = [''] * Nmax
x = [0] * (2*Nmax)
y = [0] * (2*Nmax)
st = None
dr = None
optiune = 0

def main():
    global s, optiune, st, dr
    i = 0
    n = 0
    suma = 0
    vmin = 0
    vmax = 0
    lgMax = 0

    # citire
    fin = open(inFile, 'r')
    fout = open(outFile, 'w')
    optiune = int(fin.readline())
    s = '*' + fin.readline().strip()

    s[0] = '*'
    n = len(s[1:])

    suma = 0
    for i in range(1, n+1):
        if s[i] == '1':
            suma += 1
        else:
            suma -= 1
    if suma > 0:
        if optiune == 1:
            fout.write(str(n) + "\n")
        else:
            fout.write("1\n")
        fout.close()
        return 0

    st = x[Nmax:]
    dr = y[Nmax:]

    # initializare st si dr
    for i in range(-n, n+1):
        st[i] = 10000000
        dr[i] = -10000000

    # calcul st si dr
    # st[i] = cea mai din stanga pozitie unde apare valoarea i
    # dr[i] = cea mai din dreapta pozitie unde apare valoarea i
    st[0] = dr[0] = 0
    suma = 0
    vmin = 10000000
    vmax = -10000000
    for i in range(1, n+1):
        if s[i] == '0':
            suma -= 1
        else:
            suma += 1
        st[suma] = min(st[suma], i)
        dr[suma] = max(dr[suma], i)
        vmin = min(vmin, suma)
        vmax = max(vmax, suma)

    # lungimea maxima a secventei
    lgMax = 0
    for i in range(vmin, vmax):
        lgMax = max(lgMax, dr[i+1] - st[i])

    # numarul de aparitii ale secventei maximale
    s0 = 0
    s1 = 0
    suma = 0
    for i in range(1, lgMax+1):
        if s[i] == '0':
            s0 += 1
        else:
            s1 += 1
    if s1 > s0:
        suma += 1
    for i in range(lgMax+1, n):
        if s[i-lgMax] == '0':
            s0 -= 1
        else:
            s1 -= 1
        if s[i] == '0':
            s0 += 1
        else:
            s1 += 1
        if s1 > s0:
            suma += 1

    if optiune == 1:
        fout.write(str(lgMax) + "\n")
    else:
        fout.write(str(suma) + "\n")
    fout.close()
    fin.close()
    return 0

if __name__ == "__main__":
    main()
</syntaxhighlight>