QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#639909#6129. Magic MultiplicationhhdhhAC ✓26ms5472kbC++232.9kb2024-10-13 23:50:532024-10-13 23:50:54

Judging History

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

  • [2024-10-13 23:50:54]
  • 评测
  • 测评结果:AC
  • 用时:26ms
  • 内存:5472kb
  • [2024-10-13 23:50:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

// #define endl '\n'
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define rept(i, a, ne) for(int i = (a); ~i ; i=ne[i])
#define debug(x) cout<<#x<<": "<<x<<endl
#define fi first
#define sec second
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
typedef long double  LD;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int,int>PII;
const int N=2e5+10;
LL n,m;
int a[N],b[N];
string s;
LL len;
LL get(int x)
{
    return s[x]-'0';
}
bool op(int x)
{
    int n2=0;
    rep(i,2,n)
    a[i]=-1;
    a[1]=x;
    rep(i,1,len)
    {
        if(get(i)%x==0)
        {
            b[++n2]=get(i)/x;
            if(b[n2]>9)
            return 0;
        }
        else if(i!=len&&get(i)&&(get(i)*10+get(i+1))%x==0)
        {

            b[++n2]=(get(i)*10+get(i+1))/x;
            if(b[n2]>9)
            return 0;
            i++;
        }
        else
        return 0;

        if(n2==m)
        break;
    }

    if(n2<m)
    return 0;
    int n1=0;
    int p=0;
    int sum=0;
    rep(i,1,len)
    {
        if(sum>n*m)
        return 0;
        if(sum%m==0)
        ++n1;
        ++p;
        if(b[p]==0)
        {
            if(get(i)!=0)
            {
                return 0;
            }
        }
        else if(get(i)%b[p]==0)
        {
            if(a[n1]!=-1)
            {
                if(a[n1]!=get(i)/b[p])
                return 0;
            }
            else 
            {
                a[n1]=get(i)/b[p]; 
                if(a[n1]>9)
                return 0;
            }
            
        }
        else if(i!=len&&get(i)&&(get(i)*10+get(i+1))%b[p]==0)
        {
            int y=(get(i)*10+get(i+1));
            if(a[n1]!=-1)
            {
                if(a[n1]!=y/b[p])
                return 0;
            }
            else 
            {
                a[n1]=y/b[p];
                if(a[n1]>9)
                return 0;
            }
            
            i++;
        }
        else
        return 0;


        sum++;
        p%=m;
    }
    if(sum!=n*m)
    return 0;
    
    return 1;
}
void slove()
{
    cin>>n>>m;
    cin>>s;
    len=s.size();
    s='0'+s;

    if(len<n*m||len>n*m*2)
    {
        cout<<"Impossible"<<endl; 
        return;
    }

    rep(i,1,9)
    {
        if(op(i))
        {
            rep(i,1,n)
            cout<<a[i];
            cout<<' ';
            rep(i,1,m)
            cout<<b[i];
            cout<<endl;
            return;
        }
    }
    cout<<"Impossible"<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
//	cout << fixed << setprecision(9);
    int t=1;
	cin>>t;

    while(t--)
    {
        slove();
    }


    return 0;
}
//#pragma GCC optimize(2)

详细

Test #1:

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

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: 26ms
memory: 5472kb

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