제출 #1202453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202453		SSKMF	Matching (CEOI11_mat)	C++20	100 / 100	711 ms	54324 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];

pair < int , pair <int , int> > arbore[2000000];

pair <int , int> copie[1000001];
int sir[1000001] , luat[1000001];

inline void Update (const int nod , const int stanga , const int dreapta , const int valoare , const int tip)
{
    if (stanga == dreapta)
    {
        if (tip == -1) { arbore[nod] = { }; }
        else { arbore[nod] = {1 , {tip , tip}}; }
        return;
    }

    const int mijloc = (stanga + dreapta) >> 1;
    if (valoare <= mijloc) { Update(nod + 1 , stanga , mijloc , valoare , tip); }
    else { Update(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta , valoare , tip); }

    arbore[nod].first = arbore[nod + 1].first + arbore[nod + ((mijloc - stanga + 1) << 1)].first;
    arbore[nod].second.first = (1LL * arbore[nod + 1].second.first * putere[arbore[nod + ((mijloc - stanga + 1) << 1)].first].first + arbore[nod + ((mijloc - stanga + 1) << 1)].second.first) % mod_1;
    arbore[nod].second.second = (1LL * arbore[nod + 1].second.second * putere[arbore[nod + ((mijloc - stanga + 1) << 1)].first].second + arbore[nod + ((mijloc - stanga + 1) << 1)].second.second) % mod_2;
}

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]; copie[indice] = {sir[indice] , indice}; }

    sort(copie + 1 , copie + lungime + 1);

    for (int indice = 1 ; indice <= lungime ; indice++)
        { sir[copie[indice].second] = indice; }

    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        if (lungime_secventa < indice)
        { 
            Update(1 , 1 , lungime , sir[indice - lungime_secventa] , -1);

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

        Update(1 , 1 , lungime , sir[indice] , indice);

        if (arbore[1].second == 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: 9 / 9
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10