QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492771#6129. Magic MultiplicationpriudyWA 7ms4064kbC++142.1kb2024-07-26 15:58:182024-07-26 15:58:18

Judging History

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

  • [2024-07-26 15:58:18]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:4064kb
  • [2024-07-26 15:58:18]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=110005;
int n,m;
string a,b,s;
string ansa,ansb;
vector<pair<int,int> > nums;
bool check(pair<int,int> it){
	a=b="";
	a+=it.first+'0',b+=it.second+'0';
	int k=0;
	int u=0;
	for(int p=1;p<s.length()-1;p++){
		if(k>m-1)k=0,u=0;
		if(b.length()==m){
			
		if(b[k]=='0'){
			k++;
		}	
		else if((s[p]-'0') % (b[k]-'0') ==0){
		//	cout<<((s[p]-'0')/(b[k]-'0'))<<endl;
			if(u==0)a+=((s[p]-'0')/(b[k]-'0'))+'0',u=1;
			k++;
		}
		else if( ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) % (b[k]-'0') )  == 0  ){
			if(u==0)a+=( ( (s[p+1]-'0') + 10*(s[p]-'0') ) / (b[k]-'0') )+'0',u=1;
			p++;k++;
		}
		
		else return false;	
					
		}
		else {
		if(s[p]=='0'){
			b+='0';
		}	
		else if((s[p]-'0')%it.first==0){
			b+=((s[p]-'0')/it.first)+'0';
		}
		else if( ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) %it.first)  == 0  ){
			b+= ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) /it.first)+'0';
			p++;
		}
		else return false;		
			
		}
	//	cout<<a<<" "<<b<<endl;
	}
	if(a.length()!=n)return false;
	return true;
}
void solve(){
	cin>>n>>m;ansa=ansb="";
	cin>>s;
	if(s.length()<n*m||s.length()>n*m*2){
		cout<<"Impossible"<<endl;
		return;
	}
	if(s.length()==1){
		for(int i=0;i<=9;i++){
			for(int j=1;j<=9;j++){
				if(i*j==s[0]-'0'){
					cout<<i<<" "<<j<<endl;
					return;
				}
			}
		}
	}
	else {
		s+='0';
		int s1=s[0]-'0',s2=10*(s[0]-'0')+s[1]-'0';
		nums.clear();
		for(int i=0;i<=9;i++){
			for(int j=1;j<=9;j++){
				if(i*j==s1){
					nums.emplace_back(make_pair(i,j));
				}
			}
		}
		for(auto it:nums){
			if(check(it)){
				if(ansa==""){
					ansa=a,ansb=b;
				}
				else {
					if(ansa>a){
						ansa=a,ansb=b;
					}
					else if(ansa==ansb&&ansb>b){
						ansa=a,ansb=b;
					}
				}
			}
		}		
	}
	if(ansa!=""){
		cout<<ansa<<" "<<ansb<<endl;
	}
	else cout<<"Impossible"<<endl;
	return;
}
signed main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	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: 0ms
memory: 3616kb

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

input:

1025
11 18
1461416814188088414188241035153540203545200202010354520510254921495628496328028281449632871435351535402035452002020103545205102500000000000000000000000000004000000063276372366381360363618638136918454921495628496328028281449632871435492149562849632802828144963287143514614168141880884141882...

output:

Impossible
Impossible
161650357972 65354104569
Impossible
Impossible
Impossible
Impossible
4 189401911962950
Impossible
Impossible
Impossible
Impossible
3750 119080845168191642
Impossible
Impossible
Impossible
2035 145998266186
26838140969 1
Impossible
Impossible
Impossible
Impossible
Impossible
140...

result:

wrong answer 2nd lines differ - expected: '3583 5', found: 'Impossible'