QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#101399 | #6129. Magic Multiplication | diyitibu# | AC ✓ | 33ms | 10460kb | C++14 | 2.0kb | 2023-04-29 14:30:54 | 2023-04-29 14:30:56 |
Judging History
answer
#include <iostream>
#include <bits/stdc++.h>
#define int long long
using namespace std ;
const int N = 1e6 +10 ;
int read(){
int res = 0 , flag = 1 ;
char c = getchar() ;
while(!isdigit(c)) {
if(c == '-') flag = -1 ;
c = getchar() ;
}
while(isdigit(c)) {
res = (res <<1) +(res <<3)+(c ^48) ;
c = getchar() ;
}
return res *flag ;
}
void write(int x){
if(x < 0) {
putchar('-') ;
x = -x ;
}
if(x >= 10) write(x / 10) ;
putchar('0' +x %10) ;
}
void write(int x , char c){
write(x) ;
putchar(c) ;
}
int a[N] , b[N] ;
int n , m ;
int M ;
string s ;
bool check(int x){
a[1] = x ;
int j = 1 ;
for(int i = 1 ; i <= m ; i ++) {
if(j > M) return false ;
int f = s[j] - '0' ;
if(f % x == 0) {
j ++ ;
b[i] = f / x ;
}
else {
j ++;
if(j > M) return false ;
f = f * 10 + s[j] - '0' ;
if(f % x) return false ;
b[i] = f / x ;
if(b[i] >= 10) return false ;
j ++ ;
}
}
for(int i = 2 ; i <= n ; i ++) {
if(j > M) return false ;
int f = s[j] - '0' ;
if(f % b[1] == 0) a[i] = f / b[1] , j ++;
else {
j ++ ;
if(j > M) return false ;
f = f * 10 + s[j] - '0' ;
if(f % b[1]) return false;
a[i] = f / b[1] ;
j ++ ;
}
if(a[i] >= 10) return false ;
for(int k = 2 ; k <= m ; k ++) {
int f = a[i] * b[k] ;
if(j > M) return false ;
int g = s[j] - '0' ;
j ++ ;
if(f >= 10) {
if(j > M) return false ;
g = g * 10 + s[j] - '0' ;
j ++ ;
}
if(g != f) return false ;
}
}
if(j == M+1)
return true ;
else return false ;
}
void solve(){
n = read() , m = read() ;
cin >> s ;
M = s.size() ;
s = " " + s;
for(int x = 1 ; x <= 9 ; x ++) {
if(check(x)) {
for(int i = 1 ; i <= n ; i ++) write(a[i]) ;
putchar(' ') ;
for(int i = 1 ; i <= m ; i ++) write(b[i]) ;
puts("") ;
return ;
}
}
puts("Impossible") ;
}
signed main(void) {
int T ;
cin >>T;
while(T --) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 5348kb
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: 33ms
memory: 10460kb
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