oj.uz

Submission #35495

# Submission time Handle Problem Language Result Execution time Memory
35495 2017-11-23T01:19:59 Z imaxblue Multiply (CEOI17_mul) C++14
100 / 100
 36 ms 17704 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14352 KB Output is correct
2 Correct 0 ms 14352 KB Output is correct
3 Correct 0 ms 14352 KB Output is correct
4 Correct 0 ms 14352 KB Output is correct
5 Correct 0 ms 14352 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14352 KB Output is correct
2 Correct 0 ms 14352 KB Output is correct
3 Correct 0 ms 14352 KB Output is correct
4 Correct 0 ms 14352 KB Output is correct
5 Correct 0 ms 14352 KB Output is correct
6 Correct 0 ms 14352 KB Output is correct
7 Correct 0 ms 14352 KB Output is correct
8 Correct 0 ms 14352 KB Output is correct
9 Correct 0 ms 14352 KB Output is correct
10 Correct 0 ms 14352 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14352 KB Output is correct
2 Correct 0 ms 14352 KB Output is correct
3 Correct 0 ms 14352 KB Output is correct
4 Correct 0 ms 14352 KB Output is correct
5 Correct 0 ms 14352 KB Output is correct
6 Correct 0 ms 14352 KB Output is correct
7 Correct 0 ms 14352 KB Output is correct
8 Correct 0 ms 14352 KB Output is correct
9 Correct 0 ms 14352 KB Output is correct
10 Correct 0 ms 14352 KB Output is correct
11 Correct 3 ms 14876 KB Output is correct
12 Correct 3 ms 14876 KB Output is correct
13 Correct 0 ms 14652 KB Output is correct
14 Correct 3 ms 14864 KB Output is correct
15 Correct 0 ms 14512 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14352 KB Output is correct
2 Correct 0 ms 14352 KB Output is correct
3 Correct 0 ms 14352 KB Output is correct
4 Correct 0 ms 14352 KB Output is correct
5 Correct 0 ms 14352 KB Output is correct
6 Correct 0 ms 14352 KB Output is correct
7 Correct 0 ms 14352 KB Output is correct
8 Correct 0 ms 14352 KB Output is correct
9 Correct 0 ms 14352 KB Output is correct
10 Correct 0 ms 14352 KB Output is correct
11 Correct 3 ms 14876 KB Output is correct
12 Correct 3 ms 14876 KB Output is correct
13 Correct 0 ms 14652 KB Output is correct
14 Correct 3 ms 14864 KB Output is correct
15 Correct 0 ms 14512 KB Output is correct
16 Correct 13 ms 16080 KB Output is correct
17 Correct 33 ms 17704 KB Output is correct
18 Correct 36 ms 17648 KB Output is correct
19 Correct 26 ms 17704 KB Output is correct
20 Correct 33 ms 17644 KB Output is correct