Editing 2048 - mixperm (section)

= Exemplu: =
<code>mixperm.in</code>
 6
 3 2 1 4 4 5
 2 3 3 4 6 5
<code>mixperm.out</code>
 8

=== Explicație ===
Se pot interschimba secvențele care au ca poziții de început și sfârșit <code>(1,3) (1,4) (3,3) (3,4) (4,6) (5,6) (4,5) (5,5)</code>.

De exemplu, la interschimbarea secvenţei date de intervalul <code>(3,4)</code> se obţin şirurile <code>(3,2,3,4,4,5)</code> şi <code>(2,3,1,4,6,5)</code>. Al doilea şir este o permutare.


== Încărcare soluție ==

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

nmax = 10005
inFile = "mixperm.in"
outFile = "mixperm.out"

a = [0] * nmax
b = [0] * nmax
sta = [0] * nmax
dra = [0] * nmax
stb = [0] * nmax
drb = [0] * nmax
suma_st = [0] * nmax
sumb_st = [0] * nmax
suma_dr = [0] * nmax
sumb_dr = [0] * nmax
app_st = [0] * nmax
bpp_st = [0] * nmax
app_dr = [0] * nmax
bpp_dr = [0] * nmax

S = 0
sTotal = 0
sPP = 0

def Citire():
    fin = open(inFile, 'r')
    global n
    n = int(fin.readline())
    a[1:n+1] = map(int, fin.readline().split())
    b[1:n+1] = map(int, fin.readline().split())
    fin.close()

def Precalculare():
    global S, sTotal, sPP
    S = 0
    sTotal = n * (n + 1) // 2
    sPP = 1 * n * (n + 1) * (2 * n + 1) // 6
    for i in range(1, n+1):
        S = S ^ i
        sta[i] = sta[i - 1] ^ a[i]
        stb[i] = stb[i - 1] ^ b[i]
        suma_st[i] = suma_st[i - 1] + a[i]
        sumb_st[i] = sumb_st[i - 1] + b[i]
        app_st[i] = app_st[i - 1] + a[i] * a[i]
        bpp_st[i] = bpp_st[i - 1] + b[i] * b[i]
    for i in range(n, 0, -1):
        dra[i] = dra[i + 1] ^ a[i]
        drb[i] = drb[i + 1] ^ b[i]
        suma_dr[i] = suma_dr[i + 1] + a[i]
        sumb_dr[i] = sumb_dr[i + 1] + b[i]
        app_dr[i] = app_dr[i + 1] + a[i] * a[i]
        bpp_dr[i] = bpp_dr[i + 1] + b[i] * b[i]

def Valid(j, i, aSum, bSum):
    if ((S ^ sta[j - 1] ^ bSum ^ dra[i + 1]) == 0 and sTotal == suma_st[j-1] + suma_dr[i+1] + (sumb_st[i] - sumb_st[j - 1]) and sPP == app_st[j-1] + app_dr[i+1] + (bpp_st[i] - bpp_st[j - 1])):
        return True
    if ((S ^ stb[j - 1] ^ aSum ^ drb[i + 1]) == 0 and sTotal == sumb_st[j-1] + sumb_dr[i+1] + (suma_st[i] - suma_st[j - 1]) and sPP == bpp_st[j-1] + bpp_dr[i+1] + (app_st[i] - app_st[j - 1])):
        return True
    return False

def Rezolvare():
    ans = 0
    for i in range(1, n+1):
        aSum = bSum = 0
        for j in range(i, 0, -1):
            aSum = aSum ^ a[j]
            bSum = bSum ^ b[j]
            if (Valid(j, i, aSum, bSum)):
                ans += 1

    fout = open(outFile, 'w')
    fout.write(str(ans) + "\n")
    fout.close()

if __name__ == "__main__":
    Citire()
    Precalculare()
    Rezolvare()
</syntaxhighlight>