Cod sursa(job #2265820)

Utilizator preda.andreiPreda Andrei preda.andrei Data 21 octombrie 2018 18:53:08
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <cstdint>
#include <fstream>
#include <vector>

using namespace std;

size_t SamePrefixLen(const vector<int64_t> &vec, size_t left, size_t right)
{
    size_t len = 0;
    while (right + len < vec.size() && vec[left + len] == vec[right + len]) {
        len += 1;
    }
    return len;
}

vector<size_t> FindZVec(const vector<int64_t> &vec)
{
    vector<size_t> zvec(vec.size(), 0);
    size_t left = 0, right = 0;

    for (size_t i = 1; i < vec.size(); i += 1) {
        if (i > right) {
            zvec[i] = SamePrefixLen(vec, 0, i);
            left = i;
            right = i + zvec[i] - 1;
            continue;
        }

        auto other = i - left;
        auto len_to_right = right - i + 1;

        if (zvec[other] < len_to_right) {
            zvec[i] = zvec[other];
        } else {
            auto extra = SamePrefixLen(vec, len_to_right, right + 1);
            zvec[i] = len_to_right + extra;
            left = i;
            right = i + zvec[i] - 1;
        }
    }
    return zvec;
}

bool HasPeriod(const vector<size_t> &zvec,
               const vector<int64_t> &vec,
               size_t period)
{
    if (period <= 0) {
        return false;
    }

    size_t len = period;
    while (len < zvec.size() && zvec[len] >= period) {
        len += period;
    }

    auto to_check = zvec.size() - len;
    if (to_check >= period) {
        return false;
    }

    for (size_t i = 0; i < to_check; i += 1) {
        if (vec[i] != vec[len + i]) {
            return false;
        }
    }
    return true;
}

size_t FindPeriod(const vector<int64_t> &vec)
{
    auto zvec = FindZVec(vec);
    auto period = vec.size();

    for (size_t i = 1; i < vec.size(); i += 1) {
        if (HasPeriod(zvec, vec, i)) {
            period = i;
            break;
        }
    }
    return period;
}

int main()
{
    ifstream fin("reguli.in");
    ofstream fout("reguli.out");

    int n;
    fin >> n;

    vector<int64_t> vec(n - 1);
    fin >> vec[0];

    for (auto i = 1; i < n; i += 1) {
        int64_t num;
        fin >> num;
        vec[i - 1] = num - vec[i - 1];
        if (i + 1 < n) {
            vec[i] = num;
        }
    }

    auto period = FindPeriod(vec);
    fout << period << "\n";

    for (size_t i = 0; i < period; i += 1) {
        fout << vec[i] << "\n";
    }

    return 0;
}