QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#593906#6129. Magic MultiplicationKDreamAC ✓7ms5540kbC++172.6kb2024-09-27 16:48:232024-09-27 16:48:26

Judging History

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

  • [2024-09-27 16:48:26]
  • 评测
  • 测评结果:AC
  • 用时:7ms
  • 内存:5540kb
  • [2024-09-27 16:48:23]
  • 提交

answer

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

void solve()
{
    int n ,m;
    cin >> n >> m;
    string s;
    cin >> s;
    int sz = s.size();
    vector<vector<int>> ans (15),ans2(15);
    vector<int> c(sz);
    for (int i = 0;i < sz;i ++)
    {
        c[i] = s[i] - '0';
    }
    int idx = 0;
    auto work = [&] (int x) -> bool
    {
        ans[x].push_back(x);
        for (int i = 0;i < m;i ++)
        {
            if (idx < sz && c[idx] % x == 0 && c[idx] / x <= 9)
            {
                ans2[x].push_back((c[idx]) / x);
                idx ++;
            }
            else if (idx + 1 < sz && (c[idx] * 10 + c[idx + 1]) % x == 0 && (c[idx] * 10 + c[idx + 1]) / x <= 9)
            {
                ans2[x].push_back((c[idx] * 10 + c[idx + 1]) / x);
                idx += 2;
            }
            else
            {
                return false;
            }
        }
        return true;
    };
    auto check = [&] (int x) -> bool
    {
        for (int i = 1;i < n;i ++)
        {
            if (idx < sz && c[idx] % ans2[x][0] == 0 && c[idx] / ans2[x][0] <= 9)
            {
                ans[x].push_back(c[idx] / ans2[x][0]);
                idx ++;
            }
            else if (idx + 1 < sz && (c[idx] * 10 + c[idx + 1]) % ans2[x][0] == 0 && (c[idx] * 10 + c[idx + 1]) / ans2[x][0] <= 9)
            {
                ans[x].push_back((c[idx] * 10 + c[idx + 1]) / ans2[x][0]);
                idx += 2;
            }
            else
            {
                return false;
            }

            for (int j = 1;j < m;j ++)
            {
                if (idx < sz && ans[x][i] * ans2[x][j] == c[idx])
                {
                    idx ++;
                }
                else if (idx + 1 < sz && ans[x][i] * ans2[x][j] == (c[idx] * 10 + c[idx + 1]))
                {
                    idx += 2;
                }
                else
                {
                    return false;
                }
            }
        }
        return idx == sz;
    };
    for (int i = 1;i <= 9;i ++)
    {
        idx = 0;
        if (work(i) && check(i))
        {
            for (auto j:ans[i])
            {
                cout << j;
            }
            cout << " ";
            for (auto j:ans2[i])
            {
                cout << j;
            }
            cout << "\n";
            return;
        }
    }
    cout << "Impossible\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int _ = 1;
    cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 7ms
memory: 5540kb

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