QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#691774#6129. Magic MultiplicationA_Quark#AC ✓17ms5948kbC++201.9kb2024-10-31 12:57:402024-10-31 12:57:40

Judging History

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

  • [2024-10-31 12:57:40]
  • 评测
  • 测评结果:AC
  • 用时:17ms
  • 内存:5948kb
  • [2024-10-31 12:57:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//#define DEBUG

#ifdef DEBUG
const ll N = 1010;
#endif
#ifndef DEBUG
const ll N = 200100;
#endif
ll a[N], b[N];
int main()
{
	#ifdef DEBUG
	freopen("1.txt", "r", stdin);
	#endif
	#ifndef DEBUG
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	#endif
	ll z; 
	cin >> z;
	while(z--)
	{
		ll n, m;
		cin >> n >> m;
		string s;
		cin >> s;
		
		if(n == 1 && m == 1 && s == "0")
		{
			cout << "0 0\n";
			continue;
		}
		
		ll len = s.size();
		ll pos = 0;
		auto calc = [&] (ll x) {
			if(pos >= len) throw false;
			ll tmp = s[pos]-48;
			if(tmp % x == 0 && tmp / x <= 9) 
			{
				pos++;
				return tmp / x;
			}
			else
			{
				if(pos >= len-1) throw false;
				tmp *= 10;
				tmp += s[pos+1] - 48;
				if(tmp % x == 0 && tmp / x <= 9)
				{
					pos += 2;
					return tmp / x;
				}
				else throw false;
			}
			return -1ll;
		};
		auto chk = [&] (ll x, ll y) {
			if(pos >= len) throw false;
			ll tmp = s[pos]-48;
			if(tmp == x*y) 
			{
				pos++;
				return 1;
			}
			else
			{
				if(pos >= len-1) throw false;
				tmp *= 10;
				tmp += s[pos+1] - 48;
				if(tmp == x*y) 
				{
					pos += 2;
					return 1;
				}
				else return 0;
			}
			return 0;
		};
		for(ll i=1; i<=9; i++)
		{
			pos = 0;
			try
			{
				a[0] = i;
				for(ll i=0; i<m; i++)
					b[i] = calc(a[0]);
				for(ll i=1; i<n; i++)
				{
					a[i] = calc(b[0]);
					for(ll j=1; j<m; j++)
					{
						if(!chk(a[i], b[j])) throw false;
					}
				}
				
				throw true;
			}
			catch(bool &e)
			{
				if(e)
				{
					if(pos == len)
					{
						for(ll i=0; i<n; i++) cout << a[i];
						cout <<' ' ;
						for(ll i=0; i<m; i++) cout << b[i];
						cout << '\n';
						goto fin;
					}	
				}
				else
				{
					;
				}
			}
		}
		cout << "Impossible\n";
		fin:;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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