QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#266908 | #6129. Magic Multiplication | zlxFTH | AC ✓ | 12ms | 9032kb | C++17 | 3.9kb | 2023-11-26 19:28:48 | 2023-11-26 19:28:48 |
Judging History
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