QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#101399#6129. Magic Multiplicationdiyitibu#AC ✓33ms10460kbC++142.0kb2023-04-29 14:30:542023-04-29 14:30:56

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-29 14:30:56]
  • 评测
  • 测评结果:AC
  • 用时:33ms
  • 内存:10460kb
  • [2023-04-29 14:30:54]
  • 提交

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