QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#691774 | #6129. Magic Multiplication | A_Quark# | AC ✓ | 17ms | 5948kb | C++20 | 1.9kb | 2024-10-31 12:57:40 | 2024-10-31 12:57:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define DEBUG
#ifdef DEBUG
const ll N = 1010;
#endif
#ifndef DEBUG
const ll N = 200100;
#endif
ll a[N], b[N];
int main()
{
#ifdef DEBUG
freopen("1.txt", "r", stdin);
#endif
#ifndef DEBUG
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
#endif
ll z;
cin >> z;
while(z--)
{
ll n, m;
cin >> n >> m;
string s;
cin >> s;
if(n == 1 && m == 1 && s == "0")
{
cout << "0 0\n";
continue;
}
ll len = s.size();
ll pos = 0;
auto calc = [&] (ll x) {
if(pos >= len) throw false;
ll tmp = s[pos]-48;
if(tmp % x == 0 && tmp / x <= 9)
{
pos++;
return tmp / x;
}
else
{
if(pos >= len-1) throw false;
tmp *= 10;
tmp += s[pos+1] - 48;
if(tmp % x == 0 && tmp / x <= 9)
{
pos += 2;
return tmp / x;
}
else throw false;
}
return -1ll;
};
auto chk = [&] (ll x, ll y) {
if(pos >= len) throw false;
ll tmp = s[pos]-48;
if(tmp == x*y)
{
pos++;
return 1;
}
else
{
if(pos >= len-1) throw false;
tmp *= 10;
tmp += s[pos+1] - 48;
if(tmp == x*y)
{
pos += 2;
return 1;
}
else return 0;
}
return 0;
};
for(ll i=1; i<=9; i++)
{
pos = 0;
try
{
a[0] = i;
for(ll i=0; i<m; i++)
b[i] = calc(a[0]);
for(ll i=1; i<n; i++)
{
a[i] = calc(b[0]);
for(ll j=1; j<m; j++)
{
if(!chk(a[i], b[j])) throw false;
}
}
throw true;
}
catch(bool &e)
{
if(e)
{
if(pos == len)
{
for(ll i=0; i<n; i++) cout << a[i];
cout <<' ' ;
for(ll i=0; i<m; i++) cout << b[i];
cout << '\n';
goto fin;
}
}
else
{
;
}
}
}
cout << "Impossible\n";
fin:;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5748kb
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: 17ms
memory: 5948kb
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