QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#266908#6129. Magic MultiplicationzlxFTHAC ✓12ms9032kbC++173.9kb2023-11-26 19:28:482023-11-26 19:28:48

Judging History

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

  • [2023-11-26 19:28:48]
  • 评测
  • 测评结果:AC
  • 用时:12ms
  • 内存:9032kb
  • [2023-11-26 19:28:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define max_n 510101
void read(int &p)
{
    p = 0;
    int k = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            k = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        p = p * 10 + c - '0';
        c = getchar();
    }
    p *= k;
    return;
}
void write_(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
    {
        write_(x / 10);
    }
    putchar(x % 10 + '0');
}
void writesp(int x)
{
    write_(x);
    putchar(' ');
}
void writeln(int x)
{
    write_(x);
    putchar('\n');
}
int T;
int n, m;
char s[max_n];
int c[max_n];
int a[max_n], b[max_n];
int l;
int head;
int calc(int q)
{
    if(head > l)
    {
        return -1;
    }
    int p = c[head];
    if(p % q == 0)
    {
        ++head;
        return p / q;
    }
    ++head;
    if(head > l)
    {
        return -1;
    }
    p = p * 10 + c[head];
    if(p % q == 0)
    {
        ++head;
        if(p / q >= 10)
        {
            return -1;
        }
        return p / q;
    }
    return -1;
}
bool check()
{
    head = 1;
    for(int i = 1;i <= m;i++)
    {
        int p = calc(a[1]);
        if(p == -1 || (i == 1 && p == 0))
        {
            return false;
        }
        b[i] = p;
    }
    for(int i = 2;i <= n;i++)
    {
        int p = calc(b[1]);
        if(p == -1)
        {
            return false;
        }
        a[i] = p;
        for(int j = 2;j <= m;j++)
        {
            int q = a[i] * b[j];
            if(head > l)
            {
                return false;
            }
            if(q < 10)
            {
                
                if(s[head] == q + '0')
                {
                    ++head;
                    continue;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                if(head + 1 > l)
                {
                    return false;
                }
                int flag = s[head] - '0';
                ++head;
                flag = flag * 10 + s[head] - '0';
                ++head;
                if(flag != q)
                {
                    return false;
                }
            }
        }
    }
    if(head == l + 1)
    {
        return true;
    }
    return false;
}
void solution()
{
    read(n), read(m);
    scanf("%s", s + 1);
    
    bool hasans = false;
    l = strlen(s + 1);
    for(int i = 1;i <= l;i++)
    {
        c[i] = s[i] - '0';
    }
    bool allzero = true;
    for(int i = 1;i <= l;i++)
    {
        if(s[i] != '0')
        {
            allzero = false;
        }
    }
    if(allzero)
    {
        if(n == 1 && m == l)
        {
            writesp(0);
            for(int i = 1;i <= m;i++)
            {
                write_(1);
            }
            puts("");
        }
        else if(m == 1 && n == l)
        {
            for(int i = 1;i <= n;i++)
            {
                write_(1);
            }
            putchar(' ');
            puts("0");
        }
        else
        {
            puts("Impossible");
        }
        return ;
    }
    for (int i = 1; i <= 9; i++)
    {
        a[1] = i;
        if (check())
        {
            hasans = true;
            break;
        }
    }
    if (hasans)
    {
        for (int i = 1; i <= n; i++)
        {
            write_(a[i]);
        }
        printf(" ");
        for (int i = 1; i <= m; i++)
        {
            write_(b[i]);
        }
        puts("");
    }
    else
    {
        puts("Impossible");
    }
}
signed main()
{
    read(T);
    while (T--)
    {
        solution();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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