QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#533934#6129. Magic MultiplicationTomato_Fish#AC ✓16ms5632kbC++142.4kb2024-08-26 17:12:122024-08-26 17:12:14

Judging History

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

  • [2024-08-26 17:12:14]
  • 评测
  • 测评结果:AC
  • 用时:16ms
  • 内存:5632kb
  • [2024-08-26 17:12:12]
  • 提交

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