QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252846 | #6129. Magic Multiplication | sfjh | AC ✓ | 14ms | 5700kb | C++14 | 1.5kb | 2023-11-16 13:23:01 | 2023-11-16 13:23:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fer(i,a,b) for(int i=a;i<=b;i++)
#define fdr(i,a,b) for(int i=a;i>=b;i--)
const int N=2e5+10;
int n,m;
string s;
int a[N],b[N];
bool cal(){
int len=s.size(),pos=0;
fer(i,0,m-1){
if(pos==len) return false;
int x=s[pos++]-'0';
if(pos<len&&x&&x<a[0]) x=x*10+s[pos++]-'0';
if(x%a[0]||x/a[0]>9) return false;
b[i]=x/a[0];
}
// fer(i,0,m-1) cout<<b[i];
// cout<<endl;
fer(i,1,n-1){
if(pos==len) return false;
int x=s[pos++]-'0';
if(pos<len&&x&&x<b[0]) x=x*10+s[pos++]-'0';
a[i]=x/b[0];
if(x%b[0]!=0||a[i]>9) return false;
fer(j,1,m-1){
if(pos==len) return false;
x=s[pos++]-'0';
if(pos<len&&x&&x<b[j]) x=x*10+s[pos++]-'0';
if(x==0){
if(a[i]&&b[j]) return false;
}
else{
if(b[j]==0) return false;
if(x%b[j]||(x/b[j]!=a[i])) return false;
}
}
}
// cout<<"pos"<<pos<<endl;
if(pos!=len) return false;
return true;
}
bool vis(int x){
fer(i,1,9){
if(x%i==0){
a[0]=i;
if(cal()) return true;
}
}
return false;
}
bool solve(){
int x=s[0]-'0';
if(vis(x)) return true;
x=x*10+s[1]-'0';
if(vis(x)) return true;
return false;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
cin>>n>>m>>s;
if(solve()){
fer(i,0,n-1) cout<<a[i];
cout<<' ';
fer(i,0,m-1) cout<<b[i];
cout<<endl;
}
else cout<<"Impossible\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5700kb
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: 14ms
memory: 5436kb
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