QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#496996 | #6129. Magic Multiplication | ucup-team1198# | AC ✓ | 9ms | 5300kb | C++20 | 2.2kb | 2024-07-28 17:52:40 | 2024-07-28 17:52:41 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
string s;
cin >> s;
auto move_digit = [&](int i, int d) {
if (i == s.size() || i == -1)
return -1;
if (s[i] != '0' + d)
return -1;
return i + 1;
};
auto move_num = [&](int i, int x) {
if (x < 10)
return move_digit(i, x);
return move_digit(move_digit(i, x / 10), x % 10);
};
auto move_div = [&](int i, int a) {
if (i == s.size() || i == -1)
return make_pair(-1, -1);
int k = s[i] - '0';
if (k != 0 && k < a) {
++i;
if (i == s.size())
return make_pair(-1, -1);
k = k * 10 + s[i] - '0';
}
if (k % a != 0)
return make_pair(-1, -1);
return make_pair(i + 1, k / a);
};
vector<int> a(n);
vector<int> b(m);
for (a[0] = 1; a[0] < 10; ++a[0]) {
int cur_i = 0;
bool ok = true;
for (int j = 0; ok && j < m; ++j) {
auto tmp = move_div(cur_i, a[0]);
if (tmp.first == -1) {
ok = false;
break;
}
b[j] = tmp.second;
cur_i = tmp.first;
}
if (!ok || b[0] == 0)
continue;
for (int i = 1; ok && i < n; ++i) {
auto tmp = move_div(cur_i, b[0]);
if (tmp.first == -1) {
ok = false;
break;
}
a[i] = tmp.second;
cur_i = tmp.first;
for (int j = 1; ok && j < m; ++j) {
cur_i = move_num(cur_i, b[j] * a[i]);
}
if (cur_i == -1) {
ok = false;
break;
}
}
if (ok && cur_i == s.size()) {
for (int i = 0; i < n; ++i)
cout << a[i];
cout << ' ';
for (int j = 0; j < m; ++j)
cout << b[j];
cout << '\n';
return;
}
}
cout << "Impossible\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
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: 3608kb
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: 9ms
memory: 5300kb
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