QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94084 | #6129. Magic Multiplication | CSU2023# | WA | 2ms | 3668kb | C++14 | 2.5kb | 2023-04-05 11:35:17 | 2023-04-05 11:35:22 |
Judging History
answer
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
char ch; bool flag = false; res = 0;
while (ch = getchar(), !isdigit(ch) && ch != '-');
ch == '-' ? flag = true : res = ch ^ 48;
while (ch = getchar(), isdigit(ch))
res = res * 10 + ch - 48;
flag ? res = -res : 0;
}
template <class T>
inline void put(T x)
{
if (x > 9)
put(x / 10);
putchar(x % 10 + 48);
}
template <class T>
inline void CkMin(T &x, T y) {x > y ? x = y : 0;}
const int N = 2e6 + 5;
int T_data;
int a[N], b[N];
int n, m, k, now;
char s[N];
inline int check(int &p, int x)
{
if (x == 0)
{
int t = s[p] == 0 ? 10 : -1;
++p;
return t;
}
if (s[p] == 0)
{
++p;
return 0;
}
if (s[p] % x == 0 && s[p] / x <= 9)
{
int t = s[p] / x;
++p;
return t;
}
if (p + 1 <= k && (s[p] * 10 + s[p + 1]) % x == 0
&& (s[p] * 10 + s[p + 1]) / x <= 9)
{
int t = (s[p] * 10 + s[p + 1]) / x;
p += 2;
return t;
}
return -1;
}
inline bool check_zero()
{
for (int i = 1; i <= k; ++i)
if (s[i] != '0')
return false;
return true;
}
int main()
{
read(T_data);
while (T_data--)
{
read(n); read(m);
scanf("%s", s + 1);
k = strlen(s + 1);
if (check_zero() && n == 1)
{
if (k == m)
{
putchar('0'), putchar(' '), putchar('1');
for (int k = 1; k < m; ++k)
putchar('0');
putchar('\n');
}
else
puts("Impossible");
}
else
{
for (int i = 1; i <= k; ++i)
s[i] -= '0';
bool find = false;
for (int i = 1; i <= 9; ++i)
{
a[1] = i;
now = 1;
bool flag = false;
for (int j = 1; j <= m; ++j)
{
b[j] = check(now, a[1]);
if (b[j] == -1)
{
flag = true;
break ;
}
}
if (flag || (m > 1 && b[1] == 0))
continue ;
for (int j = 2; j <= n; ++j)
{
a[j] = -1;
for (int l = 1; l <= m; ++l)
{
int t = check(now, b[l]);
if (t == -1)
{
flag = true;
break ;
}
if (t == 10)
continue ;
if (a[j] != -1 && a[j] != t)
{
flag = true;
break ;
}
a[j] = t;
}
if (flag)
break ;
a[j] = 0;
}
if (flag || now <= k)
continue ;
for (int j = 1; j <= n; ++j)
putchar(a[j] + '0');
putchar(' ');
for (int j = 1; j <= m; ++j)
putchar(b[j] + '0');
putchar('\n');
find = true;
break ;
}
if (!find)
puts("Impossible");
}
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3668kb
input:
4 2 2 8101215 3 4 100000001000 2 2 80101215 3 4 1000000010000
output:
20 45 100 1000 Impossible Impossible
result:
wrong answer 1st lines differ - expected: '23 45', found: '20 45'