QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#252846#6129. Magic MultiplicationsfjhAC ✓14ms5700kbC++141.5kb2023-11-16 13:23:012023-11-16 13:23:01

Judging History

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

  • [2023-11-16 13:23:01]
  • 评测
  • 测评结果:AC
  • 用时:14ms
  • 内存:5700kb
  • [2023-11-16 13:23:01]
  • 提交

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