QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103826#6129. Magic Multiplicationdec_rainWA 44ms4644kbC++145.0kb2023-05-07 17:31:592023-05-07 17:32:03

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-07 17:32:03]
  • 评测
  • 测评结果:WA
  • 用时:44ms
  • 内存:4644kb
  • [2023-05-07 17:31:59]
  • 提交

answer

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

const int N = 200010;

int n, m;
string s;
int a[N], b[N];

string to_str(int x)
{
    string res;
    if (!x) res = "0";
    while (x)
    {
        res += (char)('0' + x % 10);
        x /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

void solve()
{
    cin >> n >> m;
    cin >> s;

    for (int a1 = 1; a1 <= 9; a1 ++)
    {
        int t = 0, cnt = 1;
        a[1] = a1;
        int p = 0;
        bool flag = false;
        for (int i = 0; i < s.size(); i ++)
        {
            t = s[i] - '0';
            if (t % a[1] == 0)
            {
//                if (a1 == 2) cout << t << '\n';
                b[cnt ++] = t / a[1];
                t = 0;
            }
            else
            {
                if (i + 1 < s.size())
                {
                    t = t * 10 + s[i + 1] - '0';
                    if (t % a[1] == 0)
                    {
                        b[cnt ++] = t / a[1];
                        t = 0;
                        i ++;
                    }
                    else break;
                }
                else break;
            }
            if (cnt > m)
            {
                flag = true;
                p = i;
                break;
            }
        }

        if (!flag) continue;
//        for (int i = 1; i <= m; i ++) cout << b[i];
//        cout << '\n';
        flag = false;
        cnt = 2;
        int j = 1;
        bool flag2 = false;
        bool suc = false;
        t = 0;
        if (n == 1)
        {
            string ans;
            for (int i = 1; i <= n; i ++)
                for (int j = 1; j <= m; j ++)
                    ans += to_str(a[i] * b[j]);

            if (ans == s)
            {
                for (int i = 1; i <= n; i ++) cout << a[i];
                cout << ' ';
                for (int i = 1; i <= m; i ++) cout << b[i];
                cout << '\n';
                return;
            }
        }
        for (int i = p + 1; i < s.size(); i ++)
        {
            if (flag2)
            {
                t = s[i] - '0';
                if (t == a[cnt - 1] * b[j])
                {
                    t = 0;
                    j ++;
                }
                else
                {
                    if (i + 1 < s.size())
                    {
                        t = t * 10 + s[i + 1] - '0';
//                        cout << t << ' ' << a[cnt - 1] << ' ' << b[j - 1] << ' ' << j << '\n';
                        if (t == a[cnt - 1] * b[j])
                        {
                            t = 0;
                            j ++;
                            i ++;
                        }
                        else break;
                    }
                    else break;
                }
                if (j > m)
                {
                    flag2 = false;
                    j = 1;
                }
            }
            else
            {
                t = s[i] - '0';
                if (t % b[j] == 0)
                {
                    a[cnt ++] = t / b[j];
                    j ++;
                    t = 0;
                    flag2 = true;
                    if (m == 1)
                    {
                        j = 1;
                        flag2 = false;
                    }
                }
                else
                {
                    if (i + 1 < s.size())
                    {
                        t = t * 10 + s[i + 1] - '0';
                        if (t % b[j] == 0)
                        {
                            a[cnt ++] = t / b[j];
                            j ++;
                            i ++;
                            flag2 = true;
                            if (m == 1)
                            {
                                j = 1;
                                flag2 = false;
                            }
                        }
                        else break;
                    }
                    else break;

                }
                if (cnt > n)
                {
                    suc = true;
                    break;
                }
            }
        }

        if (suc)
        {
            string ans;
            for (int i = 1; i <= n; i ++)
                for (int j = 1; j <= m; j ++)
                    ans += to_str(a[i] * b[j]);

            if (ans == s)
            {
                for (int i = 1; i <= n; i ++) cout << a[i];
                cout << ' ';
                for (int i = 1; i <= m; i ++) cout << b[i];
                cout << '\n';
                return;
            }
        }
    }
    cout << "Impossible\n";
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int tt;
    cin >> tt;
    while (tt --)
    {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3424kb

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
Wrong Answer
time: 44ms
memory: 4644kb

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:

wrong answer 119th lines differ - expected: '9 9691352', found: '3 27182739156'