QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#492954#6129. Magic MultiplicationpriudyAC ✓3ms4020kbC++143.8kb2024-07-26 17:26:552024-07-26 17:26:55

Judging History

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

  • [2024-07-26 17:26:55]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:4020kb
  • [2024-07-26 17:26:55]
  • 提交

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+(it.first*it.second>=10);p<s.length()-1;p++){
		
		if(k>m-1)k=0,u=0;
		
		if(b.length()==m){
	//	cout<<"p: "<<p<<"  "<<a<<" "<<b<<" u "<<u<<endl;
	//	cout<<(s[p]-'0') % (b[k]-'0')<<" "<<( ( (s[p+1]-'0') + 10*(s[p]-'0') ) % (b[k]-'0') )<<endl;
		int o=0;
		if(b[k]=='0'){o=1;
			if(u==1){
				if ( ( ((s[p]-'0')) != (a.back()-'0')*(b[k]-'0')) &&( ( ( (s[p+1]-'0') + 10*(s[p]-'0') )  ) != (a.back()-'0')*(b[k]-'0'))){
						return false;
				}	
			}
			k++;
		}	
		else if((s[p]-'0') % (b[k]-'0') ==0){
		//	cout<<((s[p]-'0')/(b[k]-'0'))<<endl;
	//	cout<<a<<" "<<b<<endl;
			if(u==0 && ((s[p]-'0')/(b[k]-'0'))<10 )
				a+=((s[p]-'0')/(b[k]-'0'))+'0',u=1,o=1;
			else if(u==1){o=1;
			//	cout<<"xiangcheng "<<(a.back()-'0')*(b[k]-'0') <<" daan"<<((s[p]-'0')/(b[k]-'0'))+'0'<<endl;
				if( ((s[p]-'0')) != (a.back()-'0')*(b[k]-'0')){
					//cout<<"eufhewuihfueifh";
					return false;
				}	
			}
			k++;
		}
		else if( ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) % (b[k]-'0') )  == 0  ){
		//cout<<a<<" "<<b<<" "<<k<<endl;
			if(p+1<s.length()-1&&u==0&& ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) / (b[k]-'0') )<10)
				a+=( ( (s[p+1]-'0') + 10*(s[p]-'0') ) / (b[k]-'0') )+'0',u=1,o=1;
			else if(u==1){o=1;
				if( ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) ) != (a.back()-'0')*(b[k]-'0')){
				//	cout<<"asjhdfbasfbah  "<<( ( (s[p+1]-'0') + 10*(s[p]-'0') ) ) <<endl;
					return false;	
				}
								
			}
			p++;k++;
		}
		else return false;	
		if(!o)return false;
		
		}
		
		else {
			int o=0;
		if(s[p]=='0'){
			o=1;
			b+='0';
		}	
		else if((s[p]-'0')%it.first==0){
			if(((s[p]-'0')/it.first)<10)
				b+=((s[p]-'0')/it.first)+'0',o=1;
			if(o==0)return false;
		}
		else if( ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) %it.first)  == 0  ){
			if(p+1<s.length()-1&&( ( (s[p+1]-'0') + 10*(s[p]-'0') ) /it.first)<10)
				b+= ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) /it.first)+'0',o=1;
			p++;
			if(o==0)return false;
		}
		else return false;		
			
		}
	
	}
	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)){
			//	cout<<"ekfhbewiuhf"<<a<<" "<<b<<endl;
				if(ansa==""){
					ansa=a,ansb=b;
				}
				else {
					if(ansa>a){
						ansa=a,ansb=b;
					}
					else if(ansa==ansb&&ansb>b){
						ansa=a,ansb=b;
					}
				}
			}
		}
		
		nums.clear();
		for(int i=0;i<=9;i++){
			for(int j=1;j<=9;j++){
				if(i*j==s2){
					nums.emplace_back(make_pair(i,j));
				}
			}
		}
		for(auto it:nums){
			if(check(it)){//cout<<"wefewfewfew"<<a<<" "<<b<<endl;
				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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3580kb

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

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