QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#105300 | #6129. Magic Multiplication | Sorting# | WA | 25ms | 3540kb | C++20 | 2.7kb | 2023-05-13 21:27:03 | 2023-05-13 21:27:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll n , m , k ;
string ret ;
string a[ 2 ] ;
int get_dig ( int x , int &tp ) {
if ( x == 0 ) {
if ( tp >= k ) { return -1 ; }
if ( ret[ tp ] != '0' ) { return -1 ; }
++ tp ;
return 0 ;
}
int val = 0 ;
while ( 1 ) {
if ( tp >= k ) { return -1 ; }
val = 10 * val + ( ret[ tp ] - '0' ) ;
++ tp ;
if ( val >= 100 ) { return -1 ; }
if ( ( val % x ) == 0 ) {
return ( val / x ) ;
}
}
}
bool check ( int fstdig ) {
for ( int i = 0 ; i < n ; ++ i ) {
a[ 0 ][ i ] = '-' ;
}
for ( int j = 0 ; j < m ; ++ j ) {
a[ 1 ][ j ] = '-' ;
}
a[ 0 ][ 0 ] = char ( '0' + fstdig ) ;
int tp = 0 , rem = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < m ; ++ j ) {
if ( a[ 0 ][ 0 ] == '0' || a[ 1 ][ 0 ] == '0' ) { return false ; }
int x , y ;
if ( a[ 0 ][ i ] != '-' ) {
x = ( a[ 0 ][ i ] - '0' ) ;
y = get_dig ( x , tp ) ;
if ( y < 0 ) { return false ; }
if ( x == 0 ) {
continue ;
}
if ( a[ 1 ][ j ] != '-' && ( a[ 1 ][ j ] - '0' ) != y ) {
return false ;
}
a[ 1 ][ j ] = char ( '0' + y ) ;
}
else {
y = ( a[ 1 ][ j ] - '0' ) ;
x = get_dig ( y , tp ) ;
if ( x < 0 ) { return false ; }
if ( y == 0 ) {
continue ;
}
if ( a[ 0 ][ i ] != '-' && ( a[ 0 ][ i ] - '0' ) != x ) {
return false ;
}
a[ 0 ][ i ] = char ( '0' + x ) ;
}
}
}
if ( a[ 0 ][ 0 ] == '0' || a[ 1 ][ 0 ] == '0' ) { return false ; }
if ( tp != k ) { return false ; }
return true ;
}
void solve ( ) {
cin >> n >> m ;
cin >> ret ;
k = ret.size ( ) ;
if ( n * m > k ) {
cout << "Impossible\n" ;
return ;
}
a[ 0 ].resize ( n ) ;
a[ 1 ].resize ( m ) ;
for ( int fstdig = 1 ; fstdig <= 9 ; ++ fstdig ) {
if ( check ( fstdig ) == true ) {
cout << a[ 0 ] << " " << a[ 1 ] << "\n" ;
return ;
}
}
cout << "Impossible\n" ;
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3332kb
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: -100
Wrong Answer
time: 25ms
memory: 3540kb
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:
wrong answer 119th lines differ - expected: '9 9691352', found: '3 KBK39?6'