QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94955 | #6129. Magic Multiplication | George_Plover# | AC ✓ | 18ms | 11828kb | C++23 | 2.5kb | 2023-04-08 14:28:28 | 2023-04-08 14:28:29 |
Judging History
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