QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90992#6129. Magic MultiplicationLiberty12619AC ✓24ms5832kbC++202.3kb2023-03-26 13:54:382023-03-26 13:54:41

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-26 13:54:41]
  • 评测
  • 测评结果:AC
  • 用时:24ms
  • 内存:5832kb
  • [2023-03-26 13:54:38]
  • 提交

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;
}


Details

Tip: Click on the bar to expand more detailed information

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