Cod sursa(job #2245181)

Utilizator papinub2Papa Valentin papinub2 Data 24 septembrie 2018 20:10:27
Problema Reguli Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <fstream>
#include <vector>
#define BASE 37
#define MOD_1 100007
#define MOD_2 100021

using namespace std;

ifstream in("reguli.in");
ofstream out("reguli.out");

int main()
{
    int n;
    in >> n;
    int rez = n - 2;

    vector<long long> nr;
    vector<long long> v(n + 1);
    vector<long long> Hash_1(n + 1), Hash_2(n + 1);
    vector<long long> cnst_1(n + 1), cnst_2(n + 1);

    in >> v[1];

    for (int i = 2; i <= n; i++)
    {
        in >> v[i];
        nr.push_back(v[i] - v[i - 1]);
    }

    cnst_1[0] = 1;
    cnst_2[0] = 1;
    Hash_1[0] = nr[0];
    Hash_2[0] = nr[0];
    for (int i = 1; i < nr.size(); i++)
    {
        Hash_1[i] = (Hash_1[i - 1] * BASE + nr[i]) % MOD_1;
        Hash_2[i] = (Hash_2[i - 1] * BASE + nr[i]) % MOD_2;

        cnst_1[i] = (cnst_1[i - 1] * BASE) % MOD_1;
        cnst_2[i] = (cnst_2[i - 1] * BASE) % MOD_2;
    }

    int st = 0;
    int dr = nr.size() - 1;

    while (st <= dr)
    {
        bool OK = true;
        bool verif = false;
        int mij = (st + dr) / 2;

        int var_1 = Hash_1[mij];
        int var_2 = Hash_2[mij];

        int last;
        for (int i = (mij + 1) * 2 - 1; i < nr.size(); i = i + mij + 1)
        {
            verif = true;
            last = i;
            if (((Hash_1[i] - (Hash_1[i - mij - 1] * cnst_1[mij + 1]) % MOD_1 + MOD_1) % MOD_1) != var_1)
            {
                OK = false;
                break;
            }

            if (((Hash_2[i] - (Hash_2[i - mij - 1] * cnst_2[mij + 1]) % MOD_2 + MOD_2) % MOD_2) != var_2)
            {
                OK = false;
                break;
            }
        }

        if (nr.size() % (mij + 1) != 0 && (mij + 1) * 2 < nr.size())
        {
            int a = ((Hash_1[nr.size() - 1] - (Hash_1[last] * cnst_1[nr.size() - 1 - last]) % MOD_1 + MOD_1) % MOD_1);
            int b = ((Hash_2[nr.size() - 1] - (Hash_2[last] * cnst_2[nr.size() - 1 - last]) % MOD_2 + MOD_2) % MOD_2);

            int ramas = nr.size() - last - 2;

            if (a != Hash_1[ramas] || b != Hash_2[ramas])
                OK = false;
        }

        if (OK == true)
        {
            if (verif == true)
                rez = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }

    out << rez + 1 << '\n';
    for (int i = 0; i < rez + 1; i++)
        out << nr[i] << '\n';
    return 0;
}