Submission #1202682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202682		SSKMF	Multiply (CEOI17_mul)	C++20	100 / 100	65 ms	9540 KiB

mul

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

inline void FFT (vector < complex <long double> >& sir , const bool invers)
{
    const int lungime = (int)sir.size();
    for (int indice = 1 , __indice = 0 ; indice < lungime ; indice++)
    {
        int putere = (lungime >> 1);
        for ( ; __indice & putere ; putere >>= 1)
            { __indice ^= putere; }

        if (indice < (__indice ^= putere))
            { swap(sir[indice] , sir[__indice]); }
    }

    for (int lungime_secventa = 2 ; lungime_secventa <= lungime ; lungime_secventa <<= 1)
    {
        const long double unghi = (invers ? -2 : 2) * M_PI / lungime_secventa;
        const complex <long double> baza(cos(unghi) , sin(unghi));

        for (int inceput = 0 ; inceput < lungime ; inceput += lungime_secventa)
        {
            complex <long double> putere = 1;
            for (int indice_1 = inceput , indice_2 = inceput + (lungime_secventa >> 1) ; indice_2 < inceput + lungime_secventa ; indice_1++ , indice_2++)
            {
                const complex <long double> factor_1 = sir[indice_1];
                const complex <long double> factor_2 = putere * sir[indice_2];
                sir[indice_1] = factor_1 + factor_2;
                sir[indice_2] = factor_1 - factor_2;
                putere *= baza;
            }
        }
    }

    if (invers) {
        for (auto& valoare : sir)
            { valoare /= lungime; }
    }
}

inline void Inmultire (vector <int>& factor_1 , vector <int>& factor_2)
{
    int lungime = 1;
    while (lungime < (int)factor_1.size() + (int)factor_2.size())
        { lungime <<= 1; }

    vector < complex <long double> > __factor_1(lungime);
    for (int indice = 0 ; indice < (int)factor_1.size() ; indice++)
        { __factor_1[indice] = factor_1[indice]; }
        
    vector < complex <long double> > __factor_2(lungime);
    for (int indice = 0 ; indice < (int)factor_2.size() ; indice++)
        { __factor_2[indice] = factor_2[indice]; }

    FFT(__factor_1 , false);
    FFT(__factor_2 , false);

    for (int indice = 0 ; indice < lungime ; indice++)
        { __factor_1[indice] *= __factor_2[indice]; }

    FFT(__factor_1 , true);

    int transport = 0;
    factor_1.resize(lungime);
    for (int indice = 0 ; indice < lungime ; indice++ , transport /= 10)
        { factor_1[indice] = (transport += (int)round(__factor_1[indice].real())) % 10; }

    for ( ; transport ; transport /= 10)
        { factor_1.push_back(transport % 10); }

    while ((int)factor_1.size() > 1 && !factor_1.back())
        { factor_1.pop_back(); }
}

char sir_1[100001] , sir_2[50001];

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

    int lungime_1 , lungime_2;
    cin >> lungime_1 >> lungime_2 >> sir_1 >> sir_2;

    vector <int> factor_1(lungime_1) , factor_2(lungime_2);
    for (int indice = 0 ; indice < lungime_1 ; indice++)
        { factor_1[indice] = sir_1[lungime_1 - 1 - indice] - '0'; }
    for (int indice = 0 ; indice < lungime_2 ; indice++)
        { factor_2[indice] = sir_2[lungime_2 - 1 - indice] - '0'; }

    Inmultire(factor_1 , factor_2);

    for (int indice = 0 ; indice < (int)factor_1.size() ; indice++)
        { sir_1[(int)factor_1.size() - 1 - indice] = factor_1[indice] + '0'; }

    cout.write(sir_1 , factor_1.size());
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30