QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94979#6129. Magic Multiplicationysghwzp#AC ✓8ms4464kbC++141.5kb2023-04-08 15:41:512023-04-08 15:41:52

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-08 15:41:52]
  • 评测
  • 测评结果:AC
  • 用时:8ms
  • 内存:4464kb
  • [2023-04-08 15:41:51]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
int n,m,a[N],b[N],flag,len,cur;
string s;
void checka(int x){
	For(i,1,m){
		//cerr<<i<<" "<<cur<<endl;
		if(cur==len)return;
		if(s[cur]<x&&s[cur]){
			if(cur+1==len)return;
			int zs=s[cur]*10+s[cur+1];
			if(zs%x)return;
			b[i]=zs/x;
			cur+=2;
		}else{
			int zs=s[cur];
			if(zs%x)return;
			b[i]=zs/x;
			cur++;
		}
	}
	a[1]=x;
	For(i,2,n){
		if(cur==len)return;
		x=b[1];
		//cerr<<cur<<" "<<(int)s[cur]<<" "<<a[i]<<endl;
		if(s[cur]<x&&s[cur]){
			if(cur+1==len)return;
			int zs=s[cur]*10+s[cur+1];
			if(zs%x)return;
			a[i]=zs/x;
			cur+=2;
		}else{
			int zs=s[cur];
			if(zs%x)return;
			a[i]=zs/x;
			cur++;
		}
		x=a[i];
		For(j,2,m){
			if(cur==len)return;
			if(s[cur]<x&&s[cur]){
				if(cur+1==len)return;
				int zs=s[cur]*10+s[cur+1];
				if(zs!=x*b[j])return;
				cur+=2;
			}else{
				int zs=s[cur];
				if(zs!=x*b[j])return;
				cur++;
			}
		}
	}
	if(cur==len){
		For(i,1,n){
			cout<<a[i];
		}
		cout<<" ";
		For(i,1,m){
			cout<<b[i];
		}
		cout<<endl;
		flag=1;
		return;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m;
		cin>>s;
		for(auto &i:s)i-='0';
		len=s.length();
		if(n*m>len){
			cout<<"Impossible\n"; continue;
		}
		flag=0;
		For(i,1,9){
			cur=0;
			checka(i);	 //return 0;
			if(flag)break;
		}
		if(!flag){
			cout<<"Impossible\n";
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3344kb

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: 8ms
memory: 4464kb

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