QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#691713#6129. Magic MultiplicationOIer_kzc#AC ✓22ms1992kbC++171.7kb2024-10-31 12:43:512024-10-31 12:43:52

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 12:43:52]
  • 评测
  • 测评结果:AC
  • 用时:22ms
  • 内存:1992kb
  • [2024-10-31 12:43:51]
  • 提交

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