QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#605117#6129. Magic MultiplicationFoedere0WA 18ms6680kbC++202.1kb2024-10-02 15:33:572024-10-02 15:33:58

Judging History

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

  • [2024-10-02 15:33:58]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:6680kb
  • [2024-10-02 15:33:57]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 200010;
typedef pair<int, int> PII;
int n, m;
int now;
string s;
int len;
int a[N], b[N];
int get(int x)
{
    if (now > len)
        return -1;
    int t = s[now] - '0';
    
    if (t % x == 0)
    {
        now++;
        return t / x;
    }
    t = t * 10 + (s[now + 1] - '0');
    if (now < len && t % x == 0)
    {
        now += 2;
        return t / x;
    }
    return -1;
}
bool check(int x)
{
    a[1] = x;
    now = 1;
    for (int i = 1; i <= m; i++)
    {
        b[i] = get(x);
        if (b[i] < 0)
            return false;
    }
    if (b[1] == 0)
        return false;
    /*if (x == 2)
    {
        for (int i = 1; i <= m; i++)
        {
            cout << b[i];
        }
        cout << endl;
    }*/
    for (int i = 2; i <= n; i++)
    {
        a[i] = get(b[1]);
        if (a[i] < 0)
            return false;
        for (int j = 2; j <= m; j++)
        {
            int t = a[i] * b[j];
            int l = 1;
            if (t >= 10)
                l = 2;
            for (int k = l - 1; k >= 0; k--)
            {
                if (now + k > len || s[now + k] - '0' != t % 10)
                    return false;
                t /= 10;
            }
            now += l;
            if (now > len + 1)
                return false;
        }
    }
    // cout << now << endl;
    return now == len + 1;
}
void solve()
{
    cin >> n >> m;
    cin >> s;
    len = s.size();
    s = ' ' + s;
    for (int i = 1; i <= 9; i++)
    {
        if (check(i))
        {
            for (int j = 1; j <= n; j++)
            {
                cout << a[j];
            }
            cout << " ";
            for (int j = 1; j <= m; j++)
            {
                cout << b[j];
            }
            cout << endl;
            return;
        }
    }
    cout << "Impossible" << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

详细

Test #1:

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

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

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'