QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#780170#6129. Magic MultiplicationLJY_ljyAC ✓38ms5024kbC++111.6kb2024-11-25 04:45:442024-11-25 04:45:46

Judging History

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

  • [2024-11-25 04:45:46]
  • 评测
  • 测评结果:AC
  • 用时:38ms
  • 内存:5024kb
  • [2024-11-25 04:45:44]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 2e5 + 10;

char str[MAXN];
int n, m, a[MAXN], b[MAXN];

int main() {
	int t; cin >> t;
	while (t--) {
		cin >> n >> m;
		cin >> str + 1;
		int Start = 1;
		bool Fflag = false;
		for (int i = 1; i <= 9; i++) {
			int j = 1;
			Start = 1;
			for (; j <= m; j++) {
				int x = str[Start] - '0', y = (str[Start] - '0') * 10 + (str[Start + 1] - '0');
				if (x % i == 0 && x <= 9 * i) {
					b[j] = x / i;
					Start++; 
				} else if (y % i == 0 && y <= 9 * i && x != 0) {
					b[j] = y / i;
					Start += 2;
				} else 
					break;
			}
			if (j > m) {
				a[1] = i;
				bool Flag = true;
				for (int ii = 2; ii <= n; ii++) {
					bool flag = false;
					for (int k = 0; k <= 9; k++) {
						int Sstart = Start, j = 1;
						for (; j <= m; j++) {
							int x = str[Sstart] - '0', y = (str[Sstart] - '0') * 10 + (str[Sstart + 1] - '0');
							if (x == k * b[j]) {
								Sstart++;
							} else if (y == k * b[j] && x != 0) {
								Sstart += 2;
							} else
								break;
						}
						if (j > m) {
							Start = Sstart;
							a[ii] = k;
							flag = true;
							break;
						}
					}
					if (!flag) {
						Flag = false;
						break;
					}
				}
				if (Flag && Start == strlen(str + 1) + 1) {
					for (int ii = 1; ii <= n; ii++) cout << a[ii];
					cout << " ";
					for (int ii = 1; ii <= m; ii++) cout << b[ii];
					cout << endl;
					Fflag = true;
					break;
				}
			}
		}
		if (!Fflag) printf("Impossible\n");
	}	
	return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3708kb

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: 38ms
memory: 5024kb

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