QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90992 | #6129. Magic Multiplication | Liberty12619 | AC ✓ | 24ms | 5832kb | C++20 | 2.3kb | 2023-03-26 13:54:38 | 2023-03-26 13:54:41 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N = 2e5+10,M=1e5,INF=1e12,mod=998244353;
char s[N];
int a[N],b[N],n,m,len;
int mp[15][105];
bool check(int mid)
{
int x = mid;
a[1]=x;
int now=1;
for(int j=1;j<=m;j++)
{
if(now>len) return false;
if(~mp[x][s[now]-'0'])
{
b[j] = mp[x][s[now]-'0'];
now++;
}
else
{
if(now>=len) return false;
int t = (s[now]-'0')*10+s[now+1]-'0';
if(~mp[x][t])
{
b[j]=mp[x][t];
now+=2;
}
else return false;
}
}
if(b[1]==0) return false;
x=b[1];
for(int i=2;i<=n;i++)
{
if(now>len) return false;
if(~mp[x][s[now]-'0'])
{
a[i] = mp[x][s[now]-'0'];
now++;
}
else
{
if(now>=len) return false;
int t = (s[now]-'0')*10+s[now+1]-'0';
if(~mp[x][t])
{
a[i]=mp[x][t];
now+=2;
}
else return false;
}
for(int j=2;j<=m;j++)
{
int t = a[i]*b[j];
if(t<10)
{
if(now>len) return false;
if(t!=s[now]-'0') return false;
now++;
}
else
{
if(now>=len) return false;
if(t!=(s[now]-'0')*10+s[now+1]-'0') return false;
now+=2;
}
}
}
return now==len+1;
}
void solve()
{
scanf("%lld%lld",&n,&m);
scanf("%s",s+1);
len=strlen(s+1);
for(int i=1;i<=9;i++)
if(check(i))
{
for(int j=1;j<=n;j++) printf("%lld",a[j]);
printf(" ");
for(int j=1;j<=m;j++) printf("%lld",b[j]);
puts("");
return ;
}
puts("Impossible");
}
signed main()
{
int T=1;
cin>>T;
memset(mp,-1,sizeof mp);
for(int i=0;i<=9;i++)
for(int j=0;j<=9;j++)
mp[i][i*j] = j;
while(T--)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 5832kb
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: 24ms
memory: 5660kb
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