QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#533934 | #6129. Magic Multiplication | Tomato_Fish# | AC ✓ | 16ms | 5632kb | C++14 | 2.4kb | 2024-08-26 17:12:12 | 2024-08-26 17:12:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
char s[N];int a[N],b[N];
int main()
{
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
scanf("%s",s+1);
int len=strlen(s+1);bool pd2=false;
for(a[1]=1;a[1]<=9;a[1]++){
for(b[1]=1;b[1]<=9;b[1]++){
for(int j=2;j<=n;j++) a[j]=-1;
for(int j=2;j<=m;j++) b[j]=-1;
int id=1;bool pd=true;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(id>len) {pd=false;break;}
if(a[i]>=0&&b[j]>=0){
int tmp=a[i]*b[j];
if(tmp<10){
if(s[id]!=tmp+'0') {pd=false;break;}
id++;
}
if(tmp>=10){
if(id==len||s[id]!=tmp/10+'0'||s[id+1]!=tmp%10+'0') {pd=false;break;}
id+=2;
}
}
else{
bool ex=false;
if(b[j]==-1) b[j]=a[i],ex=true;
if(s[id]-'0'>=b[j]||s[id]=='0'){
if((s[id]-'0')%b[j]!=0) {pd=false;break;}
a[i]=(s[id]-'0')/b[j];id++;
}
else{
if(id==len) {pd=false;break;}
if(((s[id]-'0')*10+(s[id+1]-'0'))%b[j]!=0) {pd=false;break;}
a[i]=((s[id]-'0')*10+(s[id+1]-'0'))/b[j];id+=2;
}
if(ex) swap(a[i],b[j]);
}
// printf("%d %d %d\n",i,j,id);
}
if(!pd) break;
}
if(pd&&id==len+1){
pd2=true;
for(int i=1;i<=n;i++) putchar(a[i]+'0');
putchar(' ');
for(int i=1;i<=m;i++) putchar(b[i]+'0');
putchar('\n');
break;
}
}
if(pd2) break;
}
if(!pd2) printf("Impossible\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3752kb
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: 16ms
memory: 5632kb
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