Task: | A TIMES B! |
Sender: | aalto2024i_006 |
Submission time: | 2024-10-30 16:46:51 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
#7 | ACCEPTED | 0.00 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | ACCEPTED | 0.00 s | details |
#10 | ACCEPTED | 0.00 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | ACCEPTED | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
#14 | ACCEPTED | 0.00 s | details |
#15 | ACCEPTED | 0.00 s | details |
#16 | ACCEPTED | 0.00 s | details |
#17 | ACCEPTED | 0.00 s | details |
#18 | ACCEPTED | 0.00 s | details |
#19 | ACCEPTED | 0.00 s | details |
#20 | ACCEPTED | 0.00 s | details |
#21 | ACCEPTED | 0.00 s | details |
#22 | ACCEPTED | 0.00 s | details |
#23 | ACCEPTED | 0.00 s | details |
#24 | ACCEPTED | 0.00 s | details |
#25 | ACCEPTED | 0.00 s | details |
#26 | ACCEPTED | 0.00 s | details |
#27 | ACCEPTED | 0.00 s | details |
#28 | ACCEPTED | 0.00 s | details |
#29 | ACCEPTED | 0.00 s | details |
#30 | ACCEPTED | 0.00 s | details |
#31 | ACCEPTED | 0.00 s | details |
#32 | ACCEPTED | 0.00 s | details |
#33 | ACCEPTED | 0.00 s | details |
#34 | ACCEPTED | 0.00 s | details |
#35 | ACCEPTED | 0.00 s | details |
#36 | ACCEPTED | 0.00 s | details |
#37 | ACCEPTED | 0.00 s | details |
#38 | ACCEPTED | 0.00 s | details |
#39 | ACCEPTED | 0.00 s | details |
#40 | ACCEPTED | 0.00 s | details |
#41 | ACCEPTED | 0.00 s | details |
#42 | ACCEPTED | 0.00 s | details |
#43 | ACCEPTED | 0.00 s | details |
#44 | ACCEPTED | 0.00 s | details |
#45 | ACCEPTED | 0.00 s | details |
#46 | ACCEPTED | 0.00 s | details |
#47 | ACCEPTED | 0.00 s | details |
#48 | ACCEPTED | 0.00 s | details |
#49 | ACCEPTED | 0.00 s | details |
#50 | ACCEPTED | 0.00 s | details |
#51 | ACCEPTED | 0.00 s | details |
#52 | ACCEPTED | 0.00 s | details |
#53 | ACCEPTED | 0.00 s | details |
#54 | ACCEPTED | 0.00 s | details |
#55 | ACCEPTED | 0.00 s | details |
#56 | ACCEPTED | 0.06 s | details |
#57 | ACCEPTED | 0.07 s | details |
#58 | ACCEPTED | 0.07 s | details |
#59 | ACCEPTED | 0.06 s | details |
#60 | ACCEPTED | 0.04 s | details |
#61 | ACCEPTED | 0.51 s | details |
#62 | ACCEPTED | 0.57 s | details |
#63 | ACCEPTED | 0.57 s | details |
#64 | ACCEPTED | 0.26 s | details |
#65 | ACCEPTED | 0.49 s | details |
Code
#pragma GCC optimize("O3","unroll-loops") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #include <bits/stdc++.h> using namespace std; #define int long long #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; string to_string(string s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif /** * Author: Ludo Pulles, chilli, Simon Lindholm * Date: 2019-01-09 * License: CC0 * Source: http://neerc.ifmo.ru/trains/toulouse/2017/fft2.pdf (do read, it's excellent) Accuracy bound from http://www.daemonology.net/papers/fft.pdf * Description: fft(a) computes $\hat f(k) = \sum_x a[x] \exp(2\pi i \cdot k x / N)$ for all $k$. N must be a power of 2. Useful for convolution: \texttt{conv(a, b) = c}, where $c[x] = \sum a[i]b[x-i]$. For convolution of complex numbers or more than two vectors: FFT, multiply pointwise, divide by n, reverse(start+1, end), FFT back. Rounding is safe if $(\sum a_i^2 + \sum b_i^2)\log_2{N} < 9\cdot10^{14}$ (in practice $10^{16}$; higher for random inputs). Otherwise, use NTT/FFTMod. * Time: O(N \log N) with $N = |A|+|B|$ ($\tilde 1s$ for $N=2^{22}$) * Status: somewhat tested * Details: An in-depth examination of precision for both FFT and FFTMod can be found * here (https://github.com/simonlindholm/fft-precision/blob/master/fft-precision.md) */ typedef complex<double> C; typedef vector<double> vd; void fft(vector<C>& a) { int n = sz(a), L = 31 - __builtin_clz(n); static vector<complex<long double>> R(2, 1); static vector<C> rt(2, 1); // (^ 10% faster if double) for (static int k = 2; k < n; k *= 2) { R.resize(n); rt.resize(n); auto x = polar(1.0L, acos(-1.0L) / k); rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2]; } vi rev(n); rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2; rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]); for (int k = 1; k < n; k *= 2) for (int i = 0; i < n; i += 2 * k) rep(j,0,k) { // C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled) /// include-line auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k]; /// exclude-line C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]); /// exclude-line a[i + j + k] = a[i + j] - z; a[i + j] += z; } } vd conv(const vd& a, const vd& b) { if (a.empty() || b.empty()) return {}; vd res(sz(a) + sz(b) - 1); int L = 32 - __builtin_clz(sz(res)), n = 1 << L; vector<C> in(n), out(n); copy(all(a), begin(in)); rep(i,0,sz(b)) in[i].imag(b[i]); fft(in); for (C& x : in) x *= x; rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]); fft(out); rep(i,0,sz(res)) res[i] = imag(out[i]) / (4 * n); return res; } signed main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); // RTE if input wrong datatype string sa, sb; cin >> sa >> sb; vd a, b; for (char c : sa) a.push_back(c - '0'); for (char c : sb) b.push_back(c - '0'); reverse(all(a)); reverse(all(b)); vd c = conv(a, b); // debug(a); // debug(b); // debug(c); vi cc(sz(c)); for (int i = 0; i < sz(cc); i++) { if (i < sz(c)) cc[i] += round(c[i]); if (cc[i] >= 10) { if (i + 1 >= sz(cc)) cc.push_back(0); cc[i + 1] += cc[i] / 10; cc[i] %= 10; } } reverse(all(cc)); for (auto x : cc) cout << x; }
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: ACCEPTED
input |
---|
1 40 |
correct output |
---|
40 |
user output |
---|
40 |
Test 8
Verdict: ACCEPTED
input |
---|
97 74 |
correct output |
---|
7178 |
user output |
---|
7178 |
Test 9
Verdict: ACCEPTED
input |
---|
58 8 |
correct output |
---|
464 |
user output |
---|
464 |
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: ACCEPTED
input |
---|
778 105 |
correct output |
---|
81690 |
user output |
---|
81690 |
Test 14
Verdict: ACCEPTED
input |
---|
2 989 |
correct output |
---|
1978 |
user output |
---|
1978 |
Test 15
Verdict: ACCEPTED
input |
---|
2830 5329 |
correct output |
---|
15081070 |
user output |
---|
15081070 |
Test 16
Verdict: ACCEPTED
input |
---|
9 51382 |
correct output |
---|
462438 |
user output |
---|
462438 |
Test 17
Verdict: ACCEPTED
input |
---|
25053 71372 |
correct output |
---|
1788082716 |
user output |
---|
1788082716 |
Test 18
Verdict: ACCEPTED
input |
---|
258180 674616 |
correct output |
---|
174172358880 |
user output |
---|
174172358880 |
Test 19
Verdict: ACCEPTED
input |
---|
8821 2 |
correct output |
---|
17642 |
user output |
---|
17642 |
Test 20
Verdict: ACCEPTED
input |
---|
1742712 9600618 |
correct output |
---|
16731112196016 |
user output |
---|
16731112196016 |
Test 21
Verdict: ACCEPTED
input |
---|
8898606 2936506 |
correct output |
---|
26130809910636 |
user output |
---|
26130809910636 |
Test 22
Verdict: ACCEPTED
input |
---|
82670092 60138633 |
correct output |
---|
4971666322864236 |
user output |
---|
4971666322864236 |
Test 23
Verdict: ACCEPTED
input |
---|
54746871 83822602 |
correct output |
---|
4589025178578342 |
user output |
---|
4589025178578342 |
Test 24
Verdict: ACCEPTED
input |
---|
477252461 1032684 |
correct output |
---|
492850980435324 |
user output |
---|
492850980435324 |
Test 25
Verdict: ACCEPTED
input |
---|
5932935 379 |
correct output |
---|
2248582365 |
user output |
---|
2248582365 |
Test 26
Verdict: ACCEPTED
input |
---|
620114 3126641 |
correct output |
---|
1938873857074 |
user output |
---|
1938873857074 |
Test 27
Verdict: ACCEPTED
input |
---|
452757081 222748761 |
correct output |
---|
100851078826726641 |
user output |
---|
100851078826726641 |
Test 28
Verdict: ACCEPTED
input |
---|
689748332 888826746 |
correct output |
---|
613066765490487672 |
user output |
---|
613066765490487672 |
Test 29
Verdict: ACCEPTED
input |
---|
111337 25 |
correct output |
---|
2783425 |
user output |
---|
2783425 |
Test 30
Verdict: ACCEPTED
input |
---|
809 84435378 |
correct output |
---|
68308220802 |
user output |
---|
68308220802 |
Test 31
Verdict: ACCEPTED
input |
---|
9641697369926504411 425970950212942028697061039529... |
correct output |
---|
410708299033321711216812810174... |
user output |
---|
410708299033321711216812810174... |
Test 32
Verdict: ACCEPTED
input |
---|
793769623129909085108356241071... |
correct output |
---|
264404012608186879272715560773... |
user output |
---|
264404012608186879272715560773... Truncated |
Test 33
Verdict: ACCEPTED
input |
---|
8539777831492675800 436 |
correct output |
---|
3723343134530806648800 |
user output |
---|
3723343134530806648800 |
Test 34
Verdict: ACCEPTED
input |
---|
946492187160898604892390431179... |
correct output |
---|
585982368537725512535970251461... |
user output |
---|
585982368537725512535970251461... Truncated |
Test 35
Verdict: ACCEPTED
input |
---|
874046401974324184707688863838... |
correct output |
---|
174556202198322810668657866310... |
user output |
---|
174556202198322810668657866310... Truncated |
Test 36
Verdict: ACCEPTED
input |
---|
168584663428092347854539803060... |
correct output |
---|
235958453587245776929148968707... |
user output |
---|
235958453587245776929148968707... Truncated |
Test 37
Verdict: ACCEPTED
input |
---|
279013912031336395843652482056... |
correct output |
---|
856375236460411618343887929304... |
user output |
---|
856375236460411618343887929304... Truncated |
Test 38
Verdict: ACCEPTED
input |
---|
909594443312661242668561455177... |
correct output |
---|
801297086685128929836268694647... |
user output |
---|
801297086685128929836268694647... Truncated |
Test 39
Verdict: ACCEPTED
input |
---|
521558480102200460144622364590... |
correct output |
---|
403176935665359352292583479223... |
user output |
---|
403176935665359352292583479223... |
Test 40
Verdict: ACCEPTED
input |
---|
198766521920629467015839613580... |
correct output |
---|
197951285207558548760833360414... |
user output |
---|
197951285207558548760833360414... Truncated |
Test 41
Verdict: ACCEPTED
input |
---|
388239940637354291806784217812... |
correct output |
---|
354893636094929851749498258576... |
user output |
---|
354893636094929851749498258576... Truncated |
Test 42
Verdict: ACCEPTED
input |
---|
580031950564534684773525167998... |
correct output |
---|
225288306472433597677862095876... |
user output |
---|
225288306472433597677862095876... Truncated |
Test 43
Verdict: ACCEPTED
input |
---|
673497493525004204568833306269... |
correct output |
---|
104167516519697053781119530996... |
user output |
---|
104167516519697053781119530996... Truncated |
Test 44
Verdict: ACCEPTED
input |
---|
583582406474458495157747860432... |
correct output |
---|
355985267949419682046226194863... |
user output |
---|
355985267949419682046226194863... Truncated |
Test 45
Verdict: ACCEPTED
input |
---|
154401310284121033413839709675... |
correct output |
---|
472687322036571910421947159369... |
user output |
---|
472687322036571910421947159369... Truncated |
Test 46
Verdict: ACCEPTED
input |
---|
964784520177212016698 135881607827957154173561484162... |
correct output |
---|
131096471809203739325264543904... |
user output |
---|
131096471809203739325264543904... Truncated |
Test 47
Verdict: ACCEPTED
input |
---|
506417941420848908877158785176... |
correct output |
---|
124940484872553056181800567857... |
user output |
---|
124940484872553056181800567857... Truncated |
Test 48
Verdict: ACCEPTED
input |
---|
278205703909200971326699489015... |
correct output |
---|
213362541886605761113025837459... |
user output |
---|
213362541886605761113025837459... Truncated |
Test 49
Verdict: ACCEPTED
input |
---|
488919747667763730629078434642... |
correct output |
---|
244261035002054726047225565934... |
user output |
---|
244261035002054726047225565934... Truncated |
Test 50
Verdict: ACCEPTED
input |
---|
683013292533355268532590162229... |
correct output |
---|
271255985219635665074840248062... |
user output |
---|
271255985219635665074840248062... Truncated |
Test 51
Verdict: ACCEPTED
input |
---|
701382950383712289025758984281... |
correct output |
---|
396240397875971182850884660551... |
user output |
---|
396240397875971182850884660551... Truncated |
Test 52
Verdict: ACCEPTED
input |
---|
950530137216618089651057517232... |
correct output |
---|
525100658977646195130452101103... |
user output |
---|
525100658977646195130452101103... Truncated |
Test 53
Verdict: ACCEPTED
input |
---|
758180874616256083097058082046... |
correct output |
---|
612777382638418549100062437996... |
user output |
---|
612777382638418549100062437996... Truncated |
Test 54
Verdict: ACCEPTED
input |
---|
282198270649528096385750216226... |
correct output |
---|
878945962031578099916769892430... |
user output |
---|
878945962031578099916769892430... Truncated |
Test 55
Verdict: ACCEPTED
input |
---|
374271236006180996628555027124... |
correct output |
---|
205927043926518428842129271440... |
user output |
---|
205927043926518428842129271440... Truncated |
Test 56
Verdict: ACCEPTED
input |
---|
789860669365068182777748873091... |
correct output |
---|
369460448033120451265094062370... |
user output |
---|
369460448033120451265094062370... Truncated |
Test 57
Verdict: ACCEPTED
input |
---|
826700926013863385104801713448... |
correct output |
---|
291751287859134397942962144651... |
user output |
---|
291751287859134397942962144651... Truncated |
Test 58
Verdict: ACCEPTED
input |
---|
947468718382260248801518078140... |
correct output |
---|
226868697296935607336651841496... |
user output |
---|
226868697296935607336651841496... Truncated |
Test 59
Verdict: ACCEPTED
input |
---|
177252461103268440789803954968... |
correct output |
---|
111876380249200192763403085310... |
user output |
---|
111876380249200192763403085310... Truncated |
Test 60
Verdict: ACCEPTED
input |
---|
393293577943612353036749957226... |
correct output |
---|
336630505716557163667422969707... |
user output |
---|
336630505716557163667422969707... Truncated |
Test 61
Verdict: ACCEPTED
input |
---|
320114112664152374910455416563... |
correct output |
---|
136407754249269979820422504376... |
user output |
---|
136407754249269979820422504376... Truncated |
Test 62
Verdict: ACCEPTED
input |
---|
152757081122748761316522074282... |
correct output |
---|
107712372482584798763194835348... |
user output |
---|
107712372482584798763194835348... Truncated |
Test 63
Verdict: ACCEPTED
input |
---|
889748332988826746683887083103... |
correct output |
---|
729454517423131565738173030712... |
user output |
---|
729454517423131565738173030712... Truncated |
Test 64
Verdict: ACCEPTED
input |
---|
311337350148998951898280698942... |
correct output |
---|
245742878826375358332482490843... |
user output |
---|
245742878826375358332482490843... Truncated |
Test 65
Verdict: ACCEPTED
input |
---|
709744353788876782171034561202... |
correct output |
---|
198288295923437797210097622398... |
user output |
---|
198288295923437797210097622398... Truncated |