QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94089#6129. Magic MultiplicationCSU2023#AC ✓15ms4520kbC++142.3kb2023-04-05 11:56:282023-04-05 11:56:32

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-05 11:56:32]
  • 评测
  • 测评结果:AC
  • 用时:15ms
  • 内存:4520kb
  • [2023-04-05 11:56:28]
  • 提交

answer

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	char ch; bool flag = false; res = 0;
	while (ch = getchar(), !isdigit(ch) && ch != '-');
	ch == '-' ? flag = true : res = ch ^ 48;
	while (ch = getchar(), isdigit(ch))
		res = res * 10 + ch - 48;
	flag ? res = -res : 0; 
}

template <class T>
inline void put(T x)
{
	if (x > 9)
		put(x / 10);
	putchar(x % 10 + 48);
}

template <class T>
inline void CkMin(T &x, T y) {x > y ? x = y : 0;}

const int N = 2e6 + 5;
int T_data;
int a[N], b[N];
int n, m, k, now;
char s[N];

inline int check(int &p, int x)
{
	if (x == 0)
	{
		int t = s[p] == 0 ? 10 : -1;
		++p;
		return t; 
	}
	if (s[p] == 0)
	{
		++p;
		return 0;
	}
	if (s[p] % x == 0 && s[p] / x <= 9)
	{
		int t = s[p] / x;
		++p;
		return t;
	}
	if (p + 1 <= k && (s[p] * 10 + s[p + 1]) % x == 0
		&& (s[p] * 10 + s[p + 1]) / x <= 9)
	{
		int t = (s[p] * 10 + s[p + 1]) / x;
		p += 2;
		return t;
	}
	return -1;
}

inline bool check_zero()
{
	for (int i = 1; i <= k; ++i)
		if (s[i] != '0')
			return false;
	return true;
}
	
int main()
{
	read(T_data);	
	while (T_data--)
	{
		read(n); read(m);
		scanf("%s", s + 1);	
		k = strlen(s + 1);
		if (k < 1ll * n * m)
			puts("Impossible");
		else 
		{
			for (int i = 1; i <= k; ++i)
				s[i] -= '0';
			bool find = false;
			for (int i = 1; i <= 9; ++i)
			{
				a[1] = i;
				now = 1;
				bool flag = false;
				for (int j = 1; j <= m; ++j)
				{
					b[j] = check(now, a[1]);
					if (b[j] == -1)
					{
						flag = true;
						break ;
					}
				}
				if (flag || b[1] == 0)
					continue ;
				for (int j = 2; j <= n; ++j)
				{
					a[j] = -1;
					for (int l = 1; l <= m; ++l)
					{
						int t = check(now, b[l]);
						if (t == -1)
						{
							flag = true;
							break ;
						}
						if (t == 10)
							continue ;
						if (a[j] != -1 && a[j] != t)
						{
							flag = true;
							break ;
						}
						a[j] = t;
					}	
					if (flag)
						break ;
					if (a[j] == -1)
						a[j] = 0;
				}
				if (flag || now <= k)
					continue ;
				for (int j = 1; j <= n; ++j)	
					putchar(a[j] + '0');
				putchar(' ');
				for (int j = 1; j <= m; ++j)	
					putchar(b[j] + '0');
				putchar('\n');
				find = true;
				break ;
			}
			if (!find)
				puts("Impossible");
		}
	}	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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