QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#222612#6129. Magic Multiplicationucup-team1001TL 0ms3780kbC++202.2kb2023-10-21 17:47:532023-10-21 17:47:54

Judging History

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

  • [2023-10-21 17:47:54]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3780kb
  • [2023-10-21 17:47:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define irep(i,l,r) for(int i = (l); (i) <= (r); ++ (i))
#define ll long long
inline ll read(){
	ll s = 0;
	bool w = 0;
	char ch = getchar();
	while(! isdigit(ch)){
		if(ch == '-')w = 1;
		ch = getchar();
	}
	while(isdigit(ch)){
		s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
	}
	return w ? -s : s;
}

string s;
int len;
int n,m;
vector<int>A,B;
vector<int>AA,BB;
void work(){
	if(AA.size())return;
	A.resize(n);
	string opt[10];
	int optlen[10];
	for(int c = 0; c < 10; ++ c){
		for(int i = 0; i < m; ++ i){
			int val = c * B[i];
			if(val < 10)opt[c] += val + '0';
			else opt[c] += (val / 10) + '0', opt[c] += (val % 10) + '0';
		}
		optlen[c] = opt[c].length();
	}

	int match = 0, pos = 0, ok = 0;
	
	for(int i = 0; i < n; ++ i){
		int pas = 0;
		irep(ch, 0, 9){
			int fl = 0;
			if(pos + optlen[ch] > len)continue;
			if(i == 0 && ch == 0)continue;
			for(int p = 0; p < optlen[ch]; ++ p){
				if(opt[ch][p] != s[pos + p]){
					fl = 1;
					break;
				}
			}
			if(fl == 0){
				pos = optlen[ch] + pos;
				A[i] = ch;
				fl = 1, pas = 1;
				break;
			}
		}
		if(i == n - 1 && pos != len)return;
		if(pas == 0)return;
	}
	if(AA.size() == 0){
		AA = A;
		BB = B;
	}
	
}
void dfs(int x, int a0, int cur){
	if(cur >= len)return;
	if(x == m){
		if(B[0])work();
		return;
	}

	int op1 = s[cur] - '0', op2 = (s[cur] - '0') * 10 + s[cur + 1] - '0';
	if(op1 % a0 == 0){
		B[x] = op1 / a0;
		dfs(x + 1, a0, cur + 1);
	}
	if(op2 % a0 == 0 && op2 / a0 < 10 && op2 != 0){
		B[x] = op2 / a0;
		dfs(x + 1, a0, cur + 2);
	}
}

void solve(){
	n = read(), m = read();
	A.resize(n);
	B.resize(m);
	AA.clear();
	BB.clear();
	cin >> s;
	len = s.length();
	if(1ll * n * m > s.length() || 2ll * n * m < s.length()){
		puts("Impossible");
		return;
	}
	A.push_back(0);
	for(int a0 = 1; a0 < 10; ++ a0){
		A[0] = a0;
		B.resize(m);
		dfs(0, a0, 0);
	}
	if(AA.size() == 0){
		puts("Impossible");
		return;
	}else{
		for(int x : AA)printf("%d", x);
		putchar(' ');
		for(int x : BB)printf("%d",x);
		putchar('\n');
	}
}

int main(){
	int T = read();
	while(T --){
		solve();
	}
}

详细

Test #1:

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

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
Time Limit Exceeded

input:

1025
11 18
1461416814188088414188241035153540203545200202010354520510254921495628496328028281449632871435351535402035452002020103545205102500000000000000000000000000004000000063276372366381360363618638136918454921495628496328028281449632871435492149562849632802828144963287143514614168141880884141882...

output:

Impossible
3583 5
161650357972 65354104569
597523997017 7693
Impossible
406723924695110 973937089831524
59331138450754 554
Impossible
980565699171 84748728972992
Impossible
62155650672 4241405
9458752764004792353 8717596993614
Impossible
941952596 49242258343771276739
Impossible
64053045751 41394875...

result: