QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#392264#6129. Magic MultiplicationzaochenRE 1ms7632kbC++143.7kb2024-04-17 13:31:372024-04-17 13:31:37

Judging History

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

  • [2024-04-17 13:31:37]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:7632kb
  • [2024-04-17 13:31:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
// #define int long long

const int N = 2e6 + 5;

int T;
int n, m;
int c[N];
int a[N], b[N];

signed main()
{
    ios::sync_with_stdio(false);
#ifdef DEBUG
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    // Don't stop. Don't hide. Follow the light, and you'll find tomorrow.

    cin >> T;
    while (T--)
    {
        string s;
        cin >> n >> m;
        cin >> s;
        int l = s.length();
        s = " " + s;
        for (int i = 1; i <= l; i++)
            c[i] = s[i] - '0';
        bool flag_c = false;
        for (a[1] = 1; a[1] <= 9; a[1]++)
        {
            memset(b, 0, (m + 5) * sizeof(b[0]));
            bool flag_a1 = true;
            int c_tot = 0;
            for (int j = 1; j <= m; j++)
            {
                if (((c[c_tot + 1] % a[1]) != 0) &&
                    ((c_tot == l - 1) || ((((c[c_tot + 1] * 10 + c[c_tot + 2]) % a[1]) != 0) ||
                                          ((((c[c_tot + 1] * 10 + c[c_tot + 2]) / a[1]) > 9)))))
                {
                    flag_a1 = false;
                    break;
                }
                if (c[c_tot + 1] % a[1] == 0)
                {
                    b[j] = c[c_tot + 1] / a[1];
                    c_tot++;
                }
                else
                {
                    b[j] = (c[c_tot + 1] * 10 + c[c_tot + 2]) / a[1];
                    c_tot += 2;
                    // cout << '!' << endl;
                }
            }
            if (!flag_a1 || b[1] == 0)
                continue;
            bool flag_a = true;
            // cout << c_tot << endl;
            for (int i = 2; i <= n; i++)
            {
                // cout << c_tot << endl;
                if (((c[c_tot + 1] % b[1]) != 0) &&
                    ((c_tot == l - 1) || ((((c[c_tot + 1] * 10 + c[c_tot + 2]) % b[1]) != 0) ||
                                          ((((c[c_tot + 1] * 10 + c[c_tot + 2]) / b[1]) > 9)))))
                {
                    flag_a = false;
                    break;
                }
                if (c[c_tot + 1] % b[1] == 0)
                {
                    a[i] = c[c_tot + 1] / b[1];
                    c_tot++;
                }
                else
                {
                    a[i] = (c[c_tot + 1] * 10 + c[c_tot + 2]) / b[1];
                    c_tot += 2;
                    // cout << '!' << endl;
                }
                for (int j = 2; j <= m; j++)
                {
                    // cout << i << ' ' << j << ' ' << c_tot << endl;
                    if ((a[i] * b[j] != c[c_tot + 1]) && (a[i] * b[j] != c[c_tot + 1] * 10 + c[c_tot + 2]))
                    {
                        // cout << c_tot << ' ' << i << ' ' << j << ' ' << a[i] << ' ' << b[j] << endl;
                        flag_a = false;
                        break;
                    }
                    if ((a[i] * b[j] == c[c_tot + 1]))
                        c_tot++;
                    else if (a[i] * b[j] == c[c_tot + 1] * 10 + c[c_tot + 2])
                        c_tot += 2;
                }
            }
            // for (int i = 1; i <= n; i++)
            //     cout << a[i] << " \n"[i == n];
            if (!flag_a || c_tot != l)
                continue;
            flag_c = true;
            break;
        }
        if (!flag_c)
            cout << "Impossible" << endl;
        else
        {
            for (int i = 1; i <= n; i++)
                cout << a[i];
            cout << ' ';
            for (int j = 1; j <= m; j++)
                cout << b[j];
            cout << endl;
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7632kb

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: -100
Runtime Error

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: