QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#138313#6129. Magic Multiplicationsihan_88AC ✓9ms5352kbC++141.8kb2023-08-11 14:01:212023-08-11 14:01:24

Judging History

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

  • [2023-08-11 14:01:24]
  • 评测
  • 测评结果:AC
  • 用时:9ms
  • 内存:5352kb
  • [2023-08-11 14:01:21]
  • 提交

answer

#include<cstdio>
#include<cstring>
const int N=200010;
char s[N];
int ans1[N],ans2[N];
int a[N],b[N],c[N];
inline int cmp(int *f,int *g,int l)
{
	for(int i=1;i<=l;++i) if(f[i]!=g[i]) return (f[i]<g[i])?-1:1;
	return 0;
}
int main()
{
	int T,n,m;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%s",&n,&m,s);
		int l=0;
		for(int i=0;s[i];++i) c[l++]=s[i]-'0';
		if(l<1ll*n*m||l>2ll*n*m){puts("Impossible");continue;}
		bool flag=false;
		for(a[1]=1;a[1]<=9;++a[1])
		{
			int p=0;
			bool cur=true;
			for(int i=1;i<=m;++i)
				if(p<l&&c[p]%a[1]==0&&c[p]/a[1]<10) b[i]=c[p]/a[1],++p;
				else
				{
					int t=c[p]*10+c[p+1];
					if(p+1<l&&c[p]&&t%a[1]==0&&t/a[1]<10) b[i]=t/a[1],p+=2;
					else{cur=false;break;}
				}
			if(!b[1]) cur=false;
			if(!cur) continue;
			for(int i=2;i<=n;++i) a[i]=-1;
			for(int i=2;i<=n;++i)
			{
				for(int j=1;j<=m;++j)
					if(!b[j])
					{
						if(p>=l||c[p]){cur=false;break;}
						else ++p;
					}
					else
					{
						if(p<l&&c[p]%b[j]==0&&c[p]/b[j]<10)
						{
							if(a[i]!=-1&&a[i]!=c[p]/b[j]){cur=false;break;}
							else a[i]=c[p]/b[j],++p;
						}
						else
						{
							int t=c[p]*10+c[p+1];
							if(p+1<l&&c[p]&&t%b[j]==0&&t/b[j]<10&&(a[i]==-1||a[i]==t/b[j])) a[i]=t/b[j],p+=2;
							else{cur=false;break;}
						}
					}
				if(!cur) break;
			}
			if(p!=l) cur=false;
			if(cur)
			{
				for(int i=2;i<=n;++i) if(a[i]==-1) a[i]=0;
				int res1=cmp(a,ans1,n),res2=cmp(b,ans2,m);
				if(!flag||res1==-1||(!res1&&res2==-1)) std::memcpy(ans1,a,sizeof(int)*(n+1)),std::memcpy(ans2,b,sizeof(int)*(m+1)),flag=true;
			}
		}
		if(!flag){puts("Impossible");continue;}
		for(int i=1;i<=n;++i) printf("%d",ans1[i]);
		printf(" ");
		for(int i=1;i<=m;++i) printf("%d",ans2[i]);
		puts("");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 9ms
memory: 5352kb

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