QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#138313 | #6129. Magic Multiplication | sihan_88 | AC ✓ | 9ms | 5352kb | C++14 | 1.8kb | 2023-08-11 14:01:21 | 2023-08-11 14:01:24 |
Judging History
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