Submission #1356496

#TimeUsernameProblemLanguageResultExecution timeMemory
1356496goulthenMultiply (CEOI17_mul)C++20
40 / 100
496 ms148580 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,a,b) for (int i = a; i >= b; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define pb push_back
#define all(v) (v).begin(), (v).end()

const int MAXN = 5e5+10;
const int INF = 1e18+10;
const int MOD = 1e9+7;

string add(string a, string b) {
    int carry = 0;
    string res;
    while(a.size()>0 && b.size() > 0) {
        int cur = (a.back()-'0') + (b.back()-'0')+carry;
        res += cur%10+'0';
        carry = cur/10;

        a.pop_back();
        b.pop_back();
    }
    if(a.size()==0) swap(a,b);
    while (a.size()>0) {
        int cur = a.back()-'0'+carry;
        carry = cur/10;
        res+=cur%10+'0';
        a.pop_back();
    }
    if(carry) res+="1";
    reverse(all(res));
    return res;
}

string half(string a) {
    string res;
    int carry = 0;
    for(char &x : a) {
        int val = 10*carry + (x-'0');
        if(res.size()>0 || val/2!=0) res += (val/2)+'0';
        carry = val%2;
    }
    return res;
}

string mul(string a, string b) {
    if(a=="0" || b == "0") return "0";
    if(a=="1") return b;
    if(b=="1") return a;

    if((b.back()-'0')%2==0) {
        string t = mul(a,half(b));
        return add(t,t);
    }
    else {
        b.back() = (char)(b.back()-1);
        string t = mul(a,half(b));
        return add(add(t,t),a);
    }
}

void solve() {
    int n,m; cin >> n >> m;
    string a,b; cin >> a >> b;

    cout << mul(a,b) << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
	int tt = 1;
    //cin >> tt;
    
    while(tt--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...