QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94979 | #6129. Magic Multiplication | ysghwzp# | AC ✓ | 8ms | 4464kb | C++14 | 1.5kb | 2023-04-08 15:41:51 | 2023-04-08 15:41:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
int n,m,a[N],b[N],flag,len,cur;
string s;
void checka(int x){
For(i,1,m){
//cerr<<i<<" "<<cur<<endl;
if(cur==len)return;
if(s[cur]<x&&s[cur]){
if(cur+1==len)return;
int zs=s[cur]*10+s[cur+1];
if(zs%x)return;
b[i]=zs/x;
cur+=2;
}else{
int zs=s[cur];
if(zs%x)return;
b[i]=zs/x;
cur++;
}
}
a[1]=x;
For(i,2,n){
if(cur==len)return;
x=b[1];
//cerr<<cur<<" "<<(int)s[cur]<<" "<<a[i]<<endl;
if(s[cur]<x&&s[cur]){
if(cur+1==len)return;
int zs=s[cur]*10+s[cur+1];
if(zs%x)return;
a[i]=zs/x;
cur+=2;
}else{
int zs=s[cur];
if(zs%x)return;
a[i]=zs/x;
cur++;
}
x=a[i];
For(j,2,m){
if(cur==len)return;
if(s[cur]<x&&s[cur]){
if(cur+1==len)return;
int zs=s[cur]*10+s[cur+1];
if(zs!=x*b[j])return;
cur+=2;
}else{
int zs=s[cur];
if(zs!=x*b[j])return;
cur++;
}
}
}
if(cur==len){
For(i,1,n){
cout<<a[i];
}
cout<<" ";
For(i,1,m){
cout<<b[i];
}
cout<<endl;
flag=1;
return;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--){
cin>>n>>m;
cin>>s;
for(auto &i:s)i-='0';
len=s.length();
if(n*m>len){
cout<<"Impossible\n"; continue;
}
flag=0;
For(i,1,9){
cur=0;
checka(i); //return 0;
if(flag)break;
}
if(!flag){
cout<<"Impossible\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3344kb
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: 8ms
memory: 4464kb
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