QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94955#6129. Magic MultiplicationGeorge_Plover#AC ✓18ms11828kbC++232.5kb2023-04-08 14:28:282023-04-08 14:28:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-08 14:28:29]
  • 评测
  • 测评结果:AC
  • 用时:18ms
  • 内存:11828kb
  • [2023-04-08 14:28:28]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define MAXN 2100000
using namespace std;
int T;
int n,m;
int A[MAXN],B[MAXN];
bool visA[MAXN],visB[MAXN];
char s[MAXN];
int len;

void clear_vis(){
    for(int i=1;i<=n;i++)visA[i]=0;
    for(int i=1;i<=m;i++)visB[i]=0;
}

bool check(int x,int y,char* &z){
    //cout<<x<<" "<<y<<endl;
    if(z[0]=='\0')return 0;
    if(!visA[x] && !visB[y])return 0;
    if(visA[x]&&visB[y]){
        int t = A[x]*B[y];
        if(t>=10){
            if(z[1]=='\0')return 0;
            if(z[0]-'0'==t/10 && z[1]-'0'==t%10){
                z+=2;return 1;
            }
            return 0;
        }
        else{
            if(z[0]-'0'==t){
                z+=1;return 1;
            }
            return 0;
        }
    }
    else if(visA[x]){
        int a = A[x];
        int now = z[0]-'0';
        
        if(now<a && now){
            if(z[1]=='\0')return 0;
            now = now*10 + z[1]-'0';
            z++;
        }//cout<<"now"<<now<<" "<<a<<endl;
        if(now%a==0){
            B[y]=now/a;visB[y]=1;
            z++;
            return 1;
        }
        return 0;
    }
    else if(visB[y]){
        int b = B[y];
        int now = z[0]-'0';
        if(now<b && now){
            if(z[1]=='\0')return 0;
            now = now*10 + z[1]-'0';
            z++;
        }
        //cout<<now<<" Bnow "<<b<<" "<<(z-s)<<endl;
        if(now%b==0){
            A[x]=now/b;visA[x]=1;
            z++;
            return 1;
        }
        return 0;
    }
    return 0;
}

int main(){

    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        scanf("%s",s);
        len=strlen(s);
        
        bool flag=0;
        for(int i=1;i<=9;i++){
            clear_vis();
            visA[1]=1;
            A[1]=i;
            char *str = s;
            int nsh=0;
            for(int x=1;x<=n;x++)
                for(int y=1;y<=m;y++){
                    if(!check(x,y,str)){
                        x=n+1,nsh=1;break;
                    }
                }
            if(str-s!=len)continue;
            if(nsh)continue;
            flag=1;
            break;
        }
        if(!flag){
            puts("Impossible");
        }
        else{
            for(int i=1;i<=n;i++)putchar('0'+A[i]);putchar(' ');
            for(int i=1;i<=m;i++)putchar('0'+B[i]);putchar('\n');
        }

    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 11596kb

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: 18ms
memory: 11828kb

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