Submission #35495

#	Time	Username	Problem	Language	Result	Execution time	Memory
35495		imaxblue	Multiply (CEOI17_mul)	C++14	100 / 100	36 ms	17704 KiB

mul

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pdd pair<double, double>
#define p3d pair<pdd, double>
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define p_q priority_queue
#define MN 1000000009
#define fill(a) memset(a, 0x3f3f3f3f, sizeof a)
#define PI acos(-1)

int sz=524288;
#define sq 4
vector<complex<double> > v, w;
complex<double> e[524300];
string s, t;
ll an[524300], p;
double d; int k;
int flip(int X){
    int Y=0; for (int l=0; (1 << l)<sz; ++l, X/=2) Y=Y*2+X%2; return Y;
}
vector<complex<double> > fft(vector<complex<double> > V){
    vector<complex<double> > ans[2];
    ans[0]=vector<complex<double> >(sz);
    for (int l=0; l<sz; ++l)
        ans[0][l]=V[flip(l)];
    complex<double> t;
    for (int l=1; l<sz; l*=2){
        ans[1]=vector<complex<double> >(sz);
        for (int l2=0; l2<sz; l2+=l){
            for (int l3=0; l3<l; ++l2, ++l3){
                t=ans[0][l2+l]*e[sz/l/2*l3];
                ans[1][l2]=ans[0][l2]+t;
                ans[1][l2+l]=ans[0][l2]-t;
            }
        }
        ans[0]=ans[1];
    }
    return ans[0];
}
void con(){
    reverse(s.begin(), s.end());
    reverse(t.begin(), t.end());
    for (int l=0; l<s.size(); l+=sq){
        k=0; p=1;
        for (int l2=l; l2<min(l+sq, (int)s.size()); ++l2, p*=10) k+=(s[l2]-'0')*p;
        v.pb(k);
    }
    for (int l=0; l<t.size(); l+=sq){
        k=0; p=1;
        for (int l2=l; l2<min(l+sq, (int)t.size()); ++l2, p*=10) k+=(t[l2]-'0')*p;
        w.pb(k);
        //cout << k << endl;
    }
    //cout << v.size() << ' ' << w.size() << endl;
}
int main(){
    cin >> s >> t;
    cin >> s >> t;
    con();
    sz=max(v.size(), w.size())*2;
    while(sz!=(sz&-sz)) sz++;
    for (int l=0; l<sz; ++l) e[l]=complex<double>(cos(2*PI*l/sz), sin(2*PI*l/sz));
    while(v.size()<sz) v.pb(complex<double>(0, 0));
    while(w.size()<sz) w.pb(complex<double>(0, 0));
    v=fft(v); w=fft(w);
    for (int l=0; l<sz; ++l){
        //v[l]*=w[l];
        v[l]=complex<double>(v[l].real()*w[l].real()-v[l].imag()*w[l].imag(),
                             v[l].real()*w[l].imag()+v[l].imag()*w[l].real());
    }
    v=fft(v);
    for (int l=0; l<sz; ++l) v[l]/=sz;
    reverse(v.begin()+1, v.end());
    for (int l=0; l<sz; ++l){

        an[l]=(ll)(v[l].real()+0.5);
        //cout << v[l] << endl;
    }
    s="";
    for (int l=0; l<sz+3; ++l){
        if (an[l]<0) continue;
        an[l+1]+=an[l]/10000;
        an[l]%=10000;
        for (int l2=0; l2<4; l2++, an[l]/=10) s+=char(an[l]%10+'0');
    }
    while(s.size()>1 && s[s.size()-1]<='0') s.erase(s.size()-1);
    reverse(s.begin(), s.end());
    cout << s;
    return 0;
}

Compilation message (stderr)

mul.cpp: In function 'void con()':
mul.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<s.size(); l+=sq){
                    ^
mul.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<t.size(); l+=sq){
                    ^
mul.cpp: In function 'int main()':
mul.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(v.size()<sz) v.pb(complex<double>(0, 0));
                   ^
mul.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(w.size()<sz) w.pb(complex<double>(0, 0));
                   ^

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