QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#103826 | #6129. Magic Multiplication | dec_rain | WA | 44ms | 4644kb | C++14 | 5.0kb | 2023-05-07 17:31:59 | 2023-05-07 17:32:03 |
Judging History
answer
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 200010;
int n, m;
string s;
int a[N], b[N];
string to_str(int x)
{
string res;
if (!x) res = "0";
while (x)
{
res += (char)('0' + x % 10);
x /= 10;
}
reverse(res.begin(), res.end());
return res;
}
void solve()
{
cin >> n >> m;
cin >> s;
for (int a1 = 1; a1 <= 9; a1 ++)
{
int t = 0, cnt = 1;
a[1] = a1;
int p = 0;
bool flag = false;
for (int i = 0; i < s.size(); i ++)
{
t = s[i] - '0';
if (t % a[1] == 0)
{
// if (a1 == 2) cout << t << '\n';
b[cnt ++] = t / a[1];
t = 0;
}
else
{
if (i + 1 < s.size())
{
t = t * 10 + s[i + 1] - '0';
if (t % a[1] == 0)
{
b[cnt ++] = t / a[1];
t = 0;
i ++;
}
else break;
}
else break;
}
if (cnt > m)
{
flag = true;
p = i;
break;
}
}
if (!flag) continue;
// for (int i = 1; i <= m; i ++) cout << b[i];
// cout << '\n';
flag = false;
cnt = 2;
int j = 1;
bool flag2 = false;
bool suc = false;
t = 0;
if (n == 1)
{
string ans;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
ans += to_str(a[i] * b[j]);
if (ans == s)
{
for (int i = 1; i <= n; i ++) cout << a[i];
cout << ' ';
for (int i = 1; i <= m; i ++) cout << b[i];
cout << '\n';
return;
}
}
for (int i = p + 1; i < s.size(); i ++)
{
if (flag2)
{
t = s[i] - '0';
if (t == a[cnt - 1] * b[j])
{
t = 0;
j ++;
}
else
{
if (i + 1 < s.size())
{
t = t * 10 + s[i + 1] - '0';
// cout << t << ' ' << a[cnt - 1] << ' ' << b[j - 1] << ' ' << j << '\n';
if (t == a[cnt - 1] * b[j])
{
t = 0;
j ++;
i ++;
}
else break;
}
else break;
}
if (j > m)
{
flag2 = false;
j = 1;
}
}
else
{
t = s[i] - '0';
if (t % b[j] == 0)
{
a[cnt ++] = t / b[j];
j ++;
t = 0;
flag2 = true;
if (m == 1)
{
j = 1;
flag2 = false;
}
}
else
{
if (i + 1 < s.size())
{
t = t * 10 + s[i + 1] - '0';
if (t % b[j] == 0)
{
a[cnt ++] = t / b[j];
j ++;
i ++;
flag2 = true;
if (m == 1)
{
j = 1;
flag2 = false;
}
}
else break;
}
else break;
}
if (cnt > n)
{
suc = true;
break;
}
}
}
if (suc)
{
string ans;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
ans += to_str(a[i] * b[j]);
if (ans == s)
{
for (int i = 1; i <= n; i ++) cout << a[i];
cout << ' ';
for (int i = 1; i <= m; i ++) cout << b[i];
cout << '\n';
return;
}
}
}
cout << "Impossible\n";
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tt;
cin >> tt;
while (tt --)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3424kb
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: 44ms
memory: 4644kb
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'