Rezolvare PBinfo #3198

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.

void nule(std::vector<int> &v)
{
...
}

Exemplu:

input.txt

10
0 3 8 0 0 3 8 7 0 10

output.txt

10
3 8 3 8 7 10 0 0 0 0

Codul programului

/*
    Acadnet 2017 - Etapa Interjudeteana
    Problema A - Optimize Nule
*/
#include <iostream>
#include <vector>
#include <fstream>
#include <stdlib.h>
#define INPUT_FILENAME "input.txt"
#define OUTPUT_FILENAME "output.txt"
/*
    Aceasta este singura functie pe care aveti
    voie sa o modificati / rescrieti.
*/
void nule(std::vector<int> &v)
{
    int i, j, aux, size = v.size();
    bool swaped;
    for(i = 0; i < size - 1; i++) {
        swaped = false;
        for(j = 0; j < size - i - 1; j++) {
            if(v[j] == 0) {
                aux = v[j];
                v[j] = v[j+1];
                v[j+1] = aux;
                swaped = true;
            }
        }
        if(!swaped)
            break;
    }
}
int main(void)
{
    std::vector<int> v;
    int size, i, x;
    std::ifstream input_file;
    std::ofstream output_file;
    // Read vector from input file
    input_file.open(INPUT_FILENAME);
    if(!input_file.good()) {
        std::cout << "Failed to open " << INPUT_FILENAME << std::endl;
        exit(-1);
    }
    input_file >> size;
    v.reserve(size);
    for(i = 0; i < size; i++) {
        input_file >> x;
        v.push_back(x);
    }
    input_file.close();
    // Call nule() function
    nule(v);
    // Print vector to output file
    output_file.open(OUTPUT_FILENAME);
    if(!output_file.good()) {
        std::cout << "Failed to open " << OUTPUT_FILENAME << std::endl;
        exit(-1);
    }
    output_file << size << std::endl;
    for(i = 0; i < size; i++)
        output_file << v[i] << " ";
    output_file << std::endl;
    output_file.close();
    return 0;
}