CSES - Aalto Competitive Programming 2024 - wk8 - Mon - Results
Submission details
Task:a times b
Sender:Farah
Submission time:2024-10-28 16:28:08 +0200
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#70.00 sdetails
#8ACCEPTED0.00 sdetails
#90.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#130.00 sdetails
#140.00 sdetails
#150.00 sdetails
#160.00 sdetails
#170.00 sdetails
#180.00 sdetails
#190.00 sdetails
#200.00 sdetails
#210.00 sdetails
#220.00 sdetails
#230.00 sdetails
#240.00 sdetails
#250.00 sdetails
#260.00 sdetails
#270.00 sdetails
#280.00 sdetails
#290.00 sdetails
#300.00 sdetails
#310.00 sdetails
#320.00 sdetails
#330.00 sdetails
#340.00 sdetails
#350.00 sdetails
#360.00 sdetails
#370.00 sdetails
#380.00 sdetails
#390.00 sdetails
#400.00 sdetails
#410.00 sdetails
#420.00 sdetails
#430.00 sdetails
#440.00 sdetails
#450.00 sdetails
#460.00 sdetails
#470.03 sdetails
#480.03 sdetails
#490.00 sdetails
#500.00 sdetails
#510.00 sdetails
#520.03 sdetails
#530.03 sdetails
#540.00 sdetails
#550.03 sdetails
#560.01 sdetails
#57--details
#58--details
#590.01 sdetails
#600.01 sdetails

Code

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// Helper function to add two large numbers represented as strings
string addLargeNumbers(const string &num1, const string &num2) {
    int carry = 0;
    string result;
    int n1 = num1.size(), n2 = num2.size();
    int maxLength = max(n1, n2);

    for (int i = 0; i < maxLength || carry; i++) {
        int digit1 = i < n1 ? num1[n1 - i - 1] - '0' : 0;
        int digit2 = i < n2 ? num2[n2 - i - 1] - '0' : 0;
        int sum = digit1 + digit2 + carry;
        result.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    reverse(result.begin(), result.end());
    return result;
}

// Helper function to subtract two large numbers represented as strings
string subtractLargeNumbers(const string &num1, const string &num2) {
    string result;
    int n1 = num1.size(), n2 = num2.size();
    int carry = 0;

    for (int i = 0; i < n1; i++) {
        int digit1 = num1[n1 - i - 1] - '0';
        int digit2 = i < n2 ? num2[n2 - i - 1] - '0' : 0;
        int diff = digit1 - digit2 - carry;
        if (diff < 0) {
            diff += 10;
            carry = 1;
        } else {
            carry = 0;
        }
        result.push_back(diff + '0');
    }

    while (result.size() > 1 && result.back() == '0') {
        result.pop_back();
    }
    reverse(result.begin(), result.end());
    return result;
}

// Pad a number with zeros at the end
string padZeros(const string &num, int zeros) {
    return num + string(zeros, '0');
}

// Karatsuba multiplication for large numbers represented as strings
string karatsubaMultiply(const string &num1, const string &num2) {
    int n = max(num1.size(), num2.size());
    if (n == 1) {
        int product = (num1[0] - '0') * (num2[0] - '0');
        return to_string(product);
    }

    int half = n / 2;
    string a = num1.substr(0, num1.size() - half);
    string b = num1.substr(num1.size() - half);
    string c = num2.substr(0, num2.size() - half);
    string d = num2.substr(num2.size() - half);

    string ac = karatsubaMultiply(a, c);
    string bd = karatsubaMultiply(b, d);
    string ab_plus_cd = karatsubaMultiply(addLargeNumbers(a, b), addLargeNumbers(c, d));
    string middleTerm = subtractLargeNumbers(ab_plus_cd, addLargeNumbers(ac, bd));

    return addLargeNumbers(addLargeNumbers(padZeros(ac, 2 * half), padZeros(middleTerm, half)), bd);
}

int main() {
    string a, b;
    cin >> a >> b;
    cout << karatsubaMultiply(a, b) << endl;
    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
8
5

correct output
40

user output
40

Test 2

Verdict: ACCEPTED

input
9
1

correct output
9

user output
9

Test 3

Verdict: ACCEPTED

input
9
5

correct output
45

user output
45

Test 4

Verdict: ACCEPTED

input
2
5

correct output
10

user output
10

Test 5

Verdict: ACCEPTED

input
8
7

correct output
56

user output
56

Test 6

Verdict: ACCEPTED

input
48
92

correct output
4416

user output
4416

Test 7

Verdict:

input
1
40

correct output
40

user output
-19220

Test 8

Verdict: ACCEPTED

input
97
74

correct output
7178

user output
7178

Test 9

Verdict:

input
58
8

correct output
464

user output
505264

Test 10

Verdict: ACCEPTED

input
15
24

correct output
360

user output
360

Test 11

Verdict: ACCEPTED

input
4
7

correct output
28

user output
28

Test 12

Verdict: ACCEPTED

input
906
417

correct output
377802

user output
377802

Test 13

Verdict:

input
778
105

correct output
81690

user output
74951690

Test 14

Verdict:

input
2
989

correct output
1978

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 15

Verdict:

input
2830
5329

correct output
15081070

user output
7488289270

Test 16

Verdict:

input
9
51382

correct output
462438

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 17

Verdict:

input
25053
71372

correct output
1788082716

user output
83886882716

Test 18

Verdict:

input
258180
674616

correct output
174172358880

user output
75909061090880

Test 19

Verdict:

input
8821
2

correct output
17642

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 20

Verdict:

input
1742712
9600618

correct output
16731112196016

user output
7615754612196016

Test 21

Verdict:

input
8898606
2936506

correct output
26130809910636

user output
712296376710636

Test 22

Verdict:

input
82670092
60138633

correct output
4971666322864236

user output
814290433745357436

Test 23

Verdict:

input
54746871
83822602

correct output
4589025178578342

user output
758914406315638342

Test 24

Verdict:

input
477252461
1032684

correct output
492850980435324

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 25

Verdict:

input
5932935
379

correct output
2248582365

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 26

Verdict:

input
620114
3126641

correct output
1938873857074

user output
-263571271927074

Test 27

Verdict:

input
452757081
222748761

correct output
100851078826726641

user output
8311650091895406641

Test 28

Verdict:

input
689748332
888826746

correct output
613066765490487672

user output
620643933496415872

Test 29

Verdict:

input
111337
25

correct output
2783425

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 30

Verdict:

input
809
84435378

correct output
68308220802

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 31

Verdict:

input
9641697369926504411
425970950212942028697061039529...

correct output
410708299033321711216812810174...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 32

Verdict:

input
793769623129909085108356241071...

correct output
264404012608186879272715560773...

user output
816224913250976493797520310670...
Truncated

Test 33

Verdict:

input
8539777831492675800
436

correct output
3723343134530806648800

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 34

Verdict:

input
946492187160898604892390431179...

correct output
585982368537725512535970251461...

user output
766260514808376078814925818430...
Truncated

Test 35

Verdict:

input
874046401974324184707688863838...

correct output
174556202198322810668657866310...

user output
696831405055711210762623131202...
Truncated

Test 36

Verdict:

input
168584663428092347854539803060...

correct output
235958453587245776929148968707...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 37

Verdict:

input
279013912031336395843652482056...

correct output
856375236460411618343887929304...

user output
694662848349136064235194196405...
Truncated

Test 38

Verdict:

input
909594443312661242668561455177...

correct output
801297086685128929836268694647...

user output
828273824554726665227690531940...
Truncated

Test 39

Verdict:

input
521558480102200460144622364590...

correct output
403176935665359352292583479223...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 40

Verdict:

input
198766521920629467015839613580...

correct output
197951285207558548760833360414...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 41

Verdict:

input
388239940637354291806784217812...

correct output
354893636094929851749498258576...

user output
488805864682165514537032243317...
Truncated

Test 42

Verdict:

input
580031950564534684773525167998...

correct output
225288306472433597677862095876...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 43

Verdict:

input
673497493525004204568833306269...

correct output
104167516519697053781119530996...

user output
815106016865504450480095039429...
Truncated

Test 44

Verdict:

input
583582406474458495157747860432...

correct output
355985267949419682046226194863...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 45

Verdict:

input
154401310284121033413839709675...

correct output
472687322036571910421947159369...

user output
540624694340152255722317812754...
Truncated

Test 46

Verdict:

input
964784520177212016698
135881607827957154173561484162...

correct output
131096471809203739325264543904...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 47

Verdict:

input
506417941420848908877158785176...

correct output
124940484872553056181800567857...

user output
766381253663467461811221916160...
Truncated

Test 48

Verdict:

input
278205703909200971326699489015...

correct output
213362541886605761113025837459...

user output
756482296980935859836477166766...
Truncated

Test 49

Verdict:

input
488919747667763730629078434642...

correct output
244261035002054726047225565934...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 50

Verdict:

input
683013292533355268532590162229...

correct output
271255985219635665074840248062...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 51

Verdict:

input
701382950383712289025758984281...

correct output
396240397875971182850884660551...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 52

Verdict:

input
950530137216618089651057517232...

correct output
525100658977646195130452101103...

user output
807606048600101484649667958160...
Truncated

Test 53

Verdict:

input
758180874616256083097058082046...

correct output
612777382638418549100062437996...

user output
759405629082018321275193042218...
Truncated

Test 54

Verdict:

input
282198270649528096385750216226...

correct output
878945962031578099916769892430...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 55

Verdict:

input
374271236006180996628555027124...

correct output
205927043926518428842129271440...

user output
281652370410922065098405965503...
Truncated

Test 56

Verdict:

input
789860669365068182777748873091...

correct output
369460448033120451265094062370...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 57

Verdict:

input
826700926013863385104801713448...

correct output
291751287859134397942962144651...

user output
(empty)

Test 58

Verdict:

input
947468718382260248801518078140...

correct output
226868697296935607336651841496...

user output
(empty)

Test 59

Verdict:

input
177252461103268440789803954968...

correct output
111876380249200192763403085310...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...

Test 60

Verdict:

input
393293577943612353036749957226...

correct output
336630505716557163667422969707...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string...