QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#778746 | #6129. Magic Multiplication | 999# | AC ✓ | 22ms | 8180kb | C++14 | 1.3kb | 2024-11-24 16:07:29 | 2024-11-24 16:07:29 |
Judging History
answer
#include<bits/stdc++.h>
#define For(a,b,c) for(int a=b;a<=c;++a)
typedef long long LL;
using namespace std;
const int N=2000007;
int n,m,l,b,A[N],B[N];
char S[N];
bool eat(int st,int d,int m) {
int x=0; b=0;
For(i,st,l) {
int s=S[i]-'0';
x=x*10+s;
if(x/d>=10) return 0;
if(x%d==0) {
B[++b]=x/d;
if(b==m) return 1;
x=0;
}
}
return 0;
}
bool chk() {
int x=0,k=1,u=1;
For(i,1,n) {
int la=-1,a;
For(j,1,m) {
x=0;
if(k>l) return 0;
while(k<=l) {
int s=S[k++]-'0';
x=x*10+s;
if(B[j]==0) {
if(s!=0) return 0;
else break;
}
if(x/B[j]>=10) return 0;
if(x%B[j]==0) break;
}
if(B[j]==0) a=la;
else {
if(x%B[j]!=0) return 0;
a=x/B[j];
}
if(la!=-1&&a!=la) return 0;
la=a;
}
if(la==-1) a=0;
A[i]=a;
}
if(k>l) {
For(i,1,n) printf("%d",A[i]);
printf(" ");
For(i,1,m) printf("%d",B[i]);
puts("");
return 1;
}
return 0;
}
void magic() {
scanf("%d%d%s",&n,&m,S+1);
l=strlen(S+1),b=0;
if(S[1]=='0') {
puts("Impossible");
return;
}
For(i,1,9) {
if(eat(1,i,m)) {
// puts("B?");
// For(j,1,b) printf("%d",B[j]); puts("");
if(chk()) {
return;
}
}
}
puts("Impossible");
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
magic();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7980kb
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: 22ms
memory: 8180kb
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