QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#790423 | #6129. Magic Multiplication | NineSuns | TL | 0ms | 3836kb | C++14 | 1.6kb | 2024-11-28 11:47:32 | 2024-11-28 11:47:33 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int n, m;
string c, t[10], b, a, nw;
string tx (int x) {
string res = ""; res += (char)(x%10+'0');
if (x < 10) { return res; }
return tx(x/10)+res;
}
void solve () {
cin >> n >> m >> c;
if (1ll*n*m > c.size()) {
cout << "Impossible\n"; return;
}
int o = 0;
for (int i = 1;i <= 9;i++) {
b = ""; int fl = 1, x = 0;
for (int j = 0;j < c.size();j++) {
x = x*10+(c[j]^48);
if (x >= i*10) {
fl = 0; break;
}
if (x%i == 0) {
b += (char)(x/i+'0'); x = 0;
}
if (b.size() > m) {
fl = 0; break;
}
if (b.size() == m) {
break;
}
}
if (!fl) continue;
nw = "";
for (int j = 0;j < 10;j++) {
t[j] = "";
for (int z = 0;z < b.size();z++) {
t[j] += tx((b[z]-'0')*j);
}
}
string nw = t[i], a = tx(i);
while (nw.size() < c.size()) {
int fl = 0;
for (int j = 0;j < 10;j++) {
if (nw.size()+t[j].size() <= c.size()) {
fl = 1;
for (int z = 0;z < t[j].size();z++) if (t[j][z] != c[nw.size()+z]) {
fl = 0; break;
}
if (fl) {
a += tx(j);
nw += t[j]; break;
}
}
}
if (!fl) break;
}
if (a.size() == n && nw.size() == c.size()) {
cout << a << " " << b << "\n";
return;
}
}
cout << "Impossible\n";
}
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: 0ms
memory: 3836kb
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
Time Limit Exceeded
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...