QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#691713 | #6129. Magic Multiplication | OIer_kzc# | AC ✓ | 22ms | 1992kb | C++17 | 1.7kb | 2024-10-31 12:43:51 | 2024-10-31 12:43:52 |
Judging History
answer
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#define eb emplace_back
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
constexpr int N = 1000005;
int n, m, szc;
char a[N], b[N], c[N];
int mat(int &j, int x) {
if (x == 0) {
if (c[j]) {
return -1;
}
j += 1;
return 10;
}
if (!c[j]) {
j += 1;
return 0;
}
if (!(c[j] % x)) {
return c[j++] / x;
}
if (c[j] >= x) {
return -1;
}
if (j == szc - 1) {
return -1;
}
int t = c[j] * 10 + c[j + 1];
if (t % x) {
return -1;
}
t /= x;
if (t >= 10) {
return -1;
}
j += 2;
return t;
}
bool chk(int x) {
int j = 0;
for (int i = 0, j = 0; i < m; ++i) {
b[i] = mat(j, x);
if (b[i] == -1) {
return false;
}
}
/* LOG("x: %d\n", x);
for (int i = 0; i < m; ++i) {
LOG("%d", b[i]);
}
LOG("\n"); */
j = 0;
for (int k = 0; k < n; ++k) {
a[k] = mat(j, b[0]);
if (a[k] == -1) {
return false;
}
for (int i = 1; i < m; ++i) {
int t = mat(j, b[i]);
if (t != 10 && t != a[k]) {
return false;
}
}
}
return j == szc;
}
void solve() {
scanf("%d%d%s", &n, &m, c);
szc = strlen(c);
if (szc < n * (LL)m) {
puts("Impossible");
return;
}
for (int i = 0; i < szc; ++i) {
c[i] ^= 48;
}
if (c[0] == 0) {
puts("Impossible");
return;
}
for (int x = 1; x < 10; ++x) {
if (chk(x)) {
for (int i = 0; i < n; ++i) {
printf("%d", a[i]);
}
printf(" ");
for (int i = 0; i < m; ++i) {
printf("%d", b[i]);
}
puts("");
return;
}
}
puts("Impossible");
}
int main() {
int task;
for (scanf("%d", &task); task--; ) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1552kb
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: 22ms
memory: 1992kb
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