QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#790423#6129. Magic MultiplicationNineSunsTL 0ms3836kbC++141.6kb2024-11-28 11:47:322024-11-28 11:47:33

Judging History

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

  • [2024-11-28 11:47:33]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3836kb
  • [2024-11-28 11:47:32]
  • 提交

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...

result: