QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#695000#6129. Magic Multiplicationproven#AC ✓24ms7120kbC++203.3kb2024-10-31 19:06:402024-10-31 19:06:40

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 19:06:40]
  • 评测
  • 测评结果:AC
  • 用时:24ms
  • 内存:7120kb
  • [2024-10-31 19:06:40]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    string c; cin >> c;
    int len = (int)c.size();
    vector<int> C(len + 1);
    for(int i = 1;i <= len;i++) {
        C[i] = c[i - 1] - '0';
    }
    auto check = [&] (int l, int r, int x) {
        int tmp = 0;
        for(int i = l;i <= r;i++) tmp = tmp * 10 + C[i];
        return x == tmp;
    };
    auto calc = [&] (int x) {
        array<vector<int>, 2> res{};
        vector<int> A(n + 1), B(m + 1);
        A[1] = x;
        int i = 1;
        for(int j = 1;j <= m;j++) {
            if(i > len) return res;
            int tmp = C[i];
            if(tmp < x) {
                if(tmp == 0) {
                    B[j] = 0;
                    i++;
                    continue;
                }
                if(i == len) return res;
                tmp = tmp * 10 + C[i + 1];
                if(tmp % x) return res;
                B[j] = tmp / x;
                i += 2;
            }
            else {
                if(tmp % x) return res;
                B[j] = tmp / x;
                i++;
            }
        }
//        for(int j = 1;j <= m;j++) cout << B[j];
//        cout << endl;
//        cout << i << endl;
        for(int k = 2;k <= n;k++) {
//            cout << i << endl;
            if(i > len) return res;
            int tmp = C[i];
            if(tmp < B[1]) {
                if(tmp == 0) {
                    A[k] = 0;
                    i++;
                }
                else {
                    if(i == len) return res;
                    tmp = tmp * 10 + C[i + 1];
                    if(tmp % B[1]) return res;
                    A[k] = tmp / B[1];
//                cout << tmp << " " << x << " " << A[k] << endl;
                    i += 2;
                }
            }
            else {
                if(tmp % B[1]) return res;
                A[k] = tmp / B[1];
                i++;
            }
//            cout << "k = " << k << " " << A[k] << " " << i << endl;
            for(int j = 2;j <= m;j++) {
                if(i > len) return res;
                int now = B[j] * A[k];
//                cout << "now = " << now << " " << i << endl;
                if(now < 10) {
                    if(check(i, i, now)) i++;
                    else return res;
                }
                else {
                    if(i == len) return res;
                    if(check(i, i + 1, now)) i += 2;
                    else return res;
                }
            }
//            cout << "i = " << i << "number = " << A[k] << endl;
        }
        if(i <= len) return res;
        res[0] = A, res[1] = B;
        return res;
    };
//    calc(1);
    for(int i = 1;i <= 9;i++) {
        auto ans = calc(i);
        if((int)ans[0].size() > 0) {
            for(int j = 1;j <= n;j++) cout << ans[0][j];
            cout << " ";
            for(int j = 1;j <= m;j++) cout << ans[1][j];
            cout << endl;
            return;
        }
    }
    cout << "Impossible" << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3556kb

input:

4
2 2
8101215
3 4
100000001000
2 2
80101215
3 4
1000000010000

output:

23 45
101 1000
Impossible
Impossible

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 24ms
memory: 7120kb

input:

1025
11 18
1461416814188088414188241035153540203545200202010354520510254921495628496328028281449632871435351535402035452002020103545205102500000000000000000000000000004000000063276372366381360363618638136918454921495628496328028281449632871435492149562849632802828144963287143514614168141880884141882...

output:

Impossible
3583 5
161650357972 65354104569
597523997017 7693
Impossible
406723924695110 973937089831524
59331138450754 554
4 189401911962950
980565699171 84748728972992
Impossible
62155650672 4241405
9458752764004792353 8717596993614
Impossible
941952596 49242258343771276739
Impossible
64053045751 4...

result:

ok 1025 lines