QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94084#6129. Magic MultiplicationCSU2023#WA 2ms3668kbC++142.5kb2023-04-05 11:35:172023-04-05 11:35:22

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:35:22]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3668kb
  • [2023-04-05 11:35:17]
  • 提交

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 (check_zero() && n == 1)
		{
			if (k == m)
			{
				putchar('0'), putchar(' '), putchar('1');
				for (int k = 1; k < m; ++k)
					putchar('0');
				putchar('\n');	
			}
			else 
				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 || (m > 1 && 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 ;
				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: 0
Wrong Answer
time: 2ms
memory: 3668kb

input:

4
2 2
8101215
3 4
100000001000
2 2
80101215
3 4
1000000010000

output:

20 45
100 1000
Impossible
Impossible

result:

wrong answer 1st lines differ - expected: '23 45', found: '20 45'