QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#778746#6129. Magic Multiplication999#AC ✓22ms8180kbC++141.3kb2024-11-24 16:07:292024-11-24 16:07:29

Judging History

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

  • [2024-11-24 16:07:29]
  • 评测
  • 测评结果:AC
  • 用时:22ms
  • 内存:8180kb
  • [2024-11-24 16:07:29]
  • 提交

answer

#include<bits/stdc++.h>
#define For(a,b,c) for(int a=b;a<=c;++a)
typedef long long LL;
using namespace std;
const int N=2000007;
int n,m,l,b,A[N],B[N];
char S[N];
bool eat(int st,int d,int m) {
	int x=0; b=0;
	For(i,st,l) {
		int s=S[i]-'0';
		x=x*10+s;
		if(x/d>=10) return 0;
		if(x%d==0) {
			B[++b]=x/d;
			if(b==m) return 1;
			x=0;
		}
	}
	return 0;
}
bool chk() {
	int x=0,k=1,u=1;
	For(i,1,n) {
		int la=-1,a;
		For(j,1,m) {
			x=0;
			if(k>l) return 0;
			while(k<=l) {
				int s=S[k++]-'0';
				x=x*10+s;
				if(B[j]==0) {
					if(s!=0) return 0;
					else break;
				}
				if(x/B[j]>=10) return 0;
				if(x%B[j]==0) break;
			}
			if(B[j]==0) a=la;
			else {
				if(x%B[j]!=0) return 0;
				a=x/B[j];
			}
			if(la!=-1&&a!=la) return 0;
			la=a;
		}
		if(la==-1) a=0;
		A[i]=a;
	}
	if(k>l) {
		For(i,1,n) printf("%d",A[i]);
		printf(" ");
		For(i,1,m) printf("%d",B[i]);
		puts("");
		return 1;
	}
	return 0;
}
void magic() {
	scanf("%d%d%s",&n,&m,S+1);
	l=strlen(S+1),b=0;
	if(S[1]=='0') {
		puts("Impossible");
		return;
	}
	For(i,1,9) {
		if(eat(1,i,m)) {
			// puts("B?");
			// For(j,1,b) printf("%d",B[j]); puts("");
			if(chk()) {
				return;
			}
		}
	}
	puts("Impossible");
}
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		magic();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7980kb

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: 8180kb

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