Submission #1202448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202448		SSKMF	Matching (CEOI11_mat)	C++20	63 / 100	1483 ms	74804 KiB

mat

#include <bits/stdc++.h>
using namespace std;

mt19937_64 generator(439889232);

const int mod_1(1000000007) , mod_2(998244353);
const int baza_1(13) , baza_2(11); 

pair <int , int> putere[1000001];

struct Nod {
    uint64_t prioritate = generator();
    pair <int , int> codificare = { };
    int valoare = 0 , factor = 0 , cantitate = 0;
    Nod* stanga = NULL , *dreapta = NULL;
} *radacina;

inline int size (Nod* &nod) { return nod ? nod -> cantitate : 0; }
inline pair <int , int> __hash (Nod* &nod) { return nod ? nod -> codificare : make_pair(0 , 0); }

inline void Calcul (Nod* &nod)
{
    nod -> cantitate = 1 + size(nod -> stanga) + size(nod -> dreapta);
    nod -> codificare.first = ((1LL * __hash(nod -> stanga).first * baza_1 % mod_1 + nod -> factor) * putere[size(nod -> dreapta)].first % mod_1 + __hash(nod -> dreapta).first) % mod_1;
    nod -> codificare.second = ((1LL * __hash(nod -> stanga).second * baza_2 % mod_2 + nod -> factor) * putere[size(nod -> dreapta)].second % mod_2 + __hash(nod -> dreapta).second) % mod_2;
}

inline void RotateRight (Nod* &nod)
{
    Nod* inlocuitor = nod -> dreapta;
    nod -> dreapta = inlocuitor -> stanga;
    inlocuitor -> stanga = nod;

    Calcul(nod);
    nod = inlocuitor;
    Calcul(nod);
}

inline void RotateLeft (Nod* &nod)
{
    Nod* inlocuitor = nod -> stanga;
    nod -> stanga = inlocuitor -> dreapta;
    inlocuitor -> dreapta = nod;

    Calcul(nod);
    nod = inlocuitor;
    Calcul(nod);
}

inline void Insert (Nod* &nod , const int valoare , const int factor)
{
    if (!nod)
    {
        nod = new Nod;
        nod -> valoare = valoare;
        nod -> factor = factor;
        nod -> cantitate = 1;
        nod -> codificare = {factor , factor};
        return;
    }

    if (nod -> valoare < valoare)
    {
        Insert(nod -> dreapta , valoare , factor);
        Calcul(nod);

        if (nod -> dreapta -> prioritate > nod -> prioritate)
            { RotateRight(nod); }
    }
    else
    {
        Insert(nod -> stanga , valoare , factor);
        Calcul(nod);

        if (nod -> stanga -> prioritate > nod -> prioritate)
            { RotateLeft(nod); }
    }
}

inline void Erase (Nod* &nod , const int valoare)
{
    if (!nod -> stanga && !nod -> dreapta)
    {
        delete nod;
        nod = NULL;
        return;
    }

    if (nod -> valoare < valoare)
        { Erase(nod -> dreapta , valoare); }
    else
        if (nod -> valoare > valoare)
            { Erase(nod -> stanga , valoare); }
    else
        if (!nod -> stanga || (nod -> dreapta && nod -> dreapta -> prioritate > nod -> stanga -> prioritate))
            { RotateRight(nod); Erase(nod -> stanga , valoare); }
    else
        { RotateLeft(nod); Erase(nod -> dreapta , valoare); }

    Calcul(nod);
}

int sir[1000001] , luat[1000001];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    putere[0] = {1 , 1};
    for (int indice = 1 ; indice <= 1000000 ; indice++)
    { 
        putere[indice].first = 1LL * putere[indice - 1].first * baza_1 % mod_1;
        putere[indice].second = 1LL * putere[indice - 1].second * baza_2 % mod_2;
    }

    int lungime_secventa , lungime;
    cin >> lungime_secventa >> lungime;

    pair <int , int> dorit = { } , termen = { };
    for (int indice = 1 ; indice <= lungime_secventa ; indice++)
    {
        int valoare;
        cin >> valoare;

        dorit.first = (1LL * dorit.first * baza_1 + valoare) % mod_1;
        dorit.second = (1LL * dorit.second * baza_2 + valoare) % mod_2;

        termen.first = (1LL * termen.first * baza_1 + 1) % mod_1;
        termen.second = (1LL * termen.second * baza_2 + 1) % mod_2;
    }

    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        cin >> sir[indice];

        if (lungime_secventa < indice)
        { 
            Erase(radacina , sir[indice - lungime_secventa]);

            (dorit.first += termen.first) %= mod_1;
            (dorit.second += termen.second) %= mod_2;
        }

        Insert(radacina , sir[indice] , indice);

        if (radacina -> codificare == dorit)
            { luat[++luat[0]] = indice - lungime_secventa + 1; }
    }

    cout << luat[0] << '\n';

    for (int indice = 1 ; indice <= luat[0] ; indice++)
        { cout << luat[indice] << ' '; }

    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10