QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#605117 | #6129. Magic Multiplication | Foedere0 | WA | 18ms | 6680kb | C++20 | 2.1kb | 2024-10-02 15:33:57 | 2024-10-02 15:33:58 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'