3198 - Optimize

Programul de mai jos citește din fișierul input.txt' un vector de elemente întregi și construiește în memorie (apoi scrie în fișierul output.txt) un vector care conține aceleași elemente, doar că având toate elementele egale cu 0 la final. Ordinea celorlalte elemente se păstrează. Programul dă întotdeuna rezultatul corect, însă este ineficient din punctul de vedere al timpului de execuție.

Cerința

Rolul vostru este acela de a optimiza programul, astfel încât acesta să se execute în limita de timp indicată în enunț, pentru un vector de cel mult 1 milion de elemente. Limita de memorie trebuie, de asemenea, respectată. În acest sens, este permisă modificarea (oricât de radicală) a funcției nule. Orice modificare în afara corpului acestei funcții va conduce la respingerea soluței.

Date de intrare

Fișierul de intrare input.txt conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire output.txt va conține pe prima linie numărul n, iar pe a doua linie elementele vectorului generat.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000

Important

Soluţia propusă va conţine doar definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce la erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

Exemplul 1

input.txt

10

0 3 8 0 0 3 8 7 0 10

output.txt

Datele introduse corespund restricțiilor impuse.

10

3 8 3 8 7 10 0 0 0 0

Exemplul 2

input.txt

1000001

0 1 2 3 4 5 6 7 8 9 10

output.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

# 3198 - Optimize
def validare(n, v):
    if n < 1 or n > 1000000:
        raise ValueError("Datele introduse nu corespund restricțiilor impuse.")
    if len(v) != n:
        raise IndexError("Datele introduse nu corespund restricțiilor impuse.")
    print("Datele introduse corespund restricțiilor impuse.")


def nule(v):
    size = len(v)
    for i in range(size - 1):
        swaped = False
        for j in range(size - i - 1):
            if v[j] == 0:
                v[j], v[j+1] = v[j+1], v[j]
                swaped = True
        if not swaped:
            break


def main():
    input_filename = "input.txt"
    output_filename = "output.txt"
    # Read vector from input file
    try:
        with open(input_filename, 'r') as input_file:
            size = int(input_file.readline())
            v = list(map(int, input_file.readline().split()))
            validare(size, v)
    except IOError:
        print(f"Failed to open {input_filename}")
        exit(-1)
    except (ValueError, IndexError) as e:
        print(e)
        exit(-1)
    # Call nule() function
    nule(v)
    # Print vector to output file
    try:
        with open(output_filename, 'w') as output_file:
            output_file.write(str(size) + '\n')
            output_file.write(' '.join(map(str, v)) + '\n')
    except IOError:
        print(f"Failed to open {output_filename}")
        exit(-1)


if __name__ == "__main__":
    main()