QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190220#6129. Magic MultiplicationwoshiluoWA 19ms5248kbC++203.0kb2023-09-28 15:21:422023-09-28 15:21:42

Judging History

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

  • [2023-09-28 15:21:42]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:5248kb
  • [2023-09-28 15:21:42]
  • 提交

answer

/*
 * d.cpp 2023-09-28
 * Copyright (C) 2023 Woshiluo Luo <[email protected]>
 *
 * 「Two roads diverged in a wood,and I—
 * I took the one less traveled by,
 * And that has made all the difference.」
 *
 * Distributed under terms of the GNU GNU AGPLv3+ license.
 */

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <vector>
#include <algorithm>

typedef const int cint;
typedef long long ll;
typedef unsigned long long ull;

inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/
template <class T> 
T Max( T a, T b ) { return a > b? a: b; }
template <class T> 
T Min( T a, T b ) { return a < b? a: b; }
template <class T> 
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T> 
void chk_Min( T &a, T b ) { if( b < a ) a = b; }
template <typename T>
T read() { 
	T sum = 0, fl = 1; 
	char ch = getchar();
	for (; isdigit(ch) == 0; ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}
template <class T> 
T pow( T a, int p ) {
	T res = 1;
	while( p ) {
		if( p & 1 ) 
			res = res * a;
		a = a * a;
		p >>= 1;
	}
	return res;
}/*}}}*/

const int N = 2e5 + 1e4;

int main() {
#ifdef woshiluo
	freopen( "d.in", "r", stdin );
	freopen( "d.out", "w", stdout );
#endif

	int T = read<int>();
	
	while( T -- ) {
		cint n = read<int>();
		cint m = read<int>();

		static char str[N];
		static int p[N];
		scanf( "%s", str );
		cint len = strlen(str);
		for( int i = 0; i < len; i ++ ) {
			p[i] = ( str[i] - '0' );
		}

		bool solved = false;
		for( int o = 1; o <= 9; o ++ ) {
			std::vector<int> a, b;
			a.push_back(o);
			int k = 0;
			bool flag = true;
			auto try_get = [&]( cint another ) {
				if( another == 0 ) {
					if( p[k] == 0 ) {
						k ++;
						return 0;
					}
					else {
						flag = false;
						return 0;
					}
				}
				if( p[k] == 0 ) {
					k ++;
					return 0;
				}
				if( p[k] >= another ) {
					if( k >= len || p[k] % another != 0 ) {
						flag = false;
						return 0;
					}
					cint res = p[k] / another;
					k ++;
					return res;
				}
				else {
					cint cur = p[k] * 10 + p[ k + 1 ];
					if( k + 1 >= len || cur % another != 0 ) {
						flag = false;
						return 0;
					}
					k += 2;
					return cur / another;
				}
				return 0;
			};
			for( int j = 1; j <= m; j ++ ) {
				b.push_back(try_get(a[0]));
				if( !flag )
					break;
			}
			for( int i = 1; i < n; i ++ ) {
				a.push_back(try_get(b[0]));
				if( !flag )
					break;
				for( int j = 1; j < m; j ++ ) {
					if( b[j] != try_get( a[i] ) ) {
						flag = false;
						break;
					}
					if( !flag )
						break;
				}
			}

			if( k < len ) 
				flag = false;
			if( flag ) {
				for( auto &x: a ) 
					printf( "%d", x );
				printf( " " );
				for( auto &x: b)  
					printf( "%d", x );
				solved = true;
				printf( "\n" );
				break;
			}
		}

		if( !solved ) 
			printf( "Impossible\n" );

	}
}

详细

Test #1:

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

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

input:

1025
11 18
1461416814188088414188241035153540203545200202010354520510254921495628496328028281449632871435351535402035452002020103545205102500000000000000000000000000004000000063276372366381360363618638136918454921495628496328028281449632871435492149562849632802828144963287143514614168141880884141882...

output:

Impossible
3583 5
Impossible
Impossible
Impossible
Impossible
Impossible
4 189401911962950
Impossible
Impossible
Impossible
Impossible
Impossible
941952596 49242258343771276739
Impossible
Impossible
Impossible
26838140969 1
Impossible
Impossible
Impossible
Impossible
9677 389
Impossible
337756 69295...

result:

wrong answer 3rd lines differ - expected: '161650357972 65354104569', found: 'Impossible'