QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#149579#6129. Magic Multiplicationpooty#AC ✓24ms5312kbC++202.9kb2023-08-24 21:56:412023-08-24 21:56:42

Judging History

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

  • [2023-08-24 21:56:42]
  • 评测
  • 测评结果:AC
  • 用时:24ms
  • 内存:5312kb
  • [2023-08-24 21:56:41]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); i++)
#define REPL(i,j, n) for (int i = (j); i < (n); i++)
typedef vector<int> vi;
typedef vector<vi> vvi;

int getseq(int val, vi &B, vi &reference, int starting) {
    int mxs = reference.size();
    int curidx = starting;
    for (auto x: B) {
        int gg = x*val;

        if (gg < 10) {
            if (curidx >= mxs) return -1;
            if (reference[curidx] != gg) return -1;
            curidx++;
        } else {
            int t1 = gg/10;
            int t2 = gg%10;
            if (curidx+1 >= mxs) return -1;
            if (reference[curidx] != t1 || reference[curidx+1] != t2) return -1;
            curidx+=2;
        }
    }
    return curidx;
}
void printarr(vi arr) {
    for (auto x: arr) {
        cout<<x;
    }cout<<"...\n";
}
void solve() {
    int n,m;cin>>n>>m;
    string cstr;
    vi carr;

    cin>>cstr;
     for (auto x: cstr) {
        carr.push_back(x - '0');
    }
    int len = cstr.size();
    REPL(adig, 1, 10) {
        int currentplace = 0;
        bool good = true;
        vi possibleB;
        REP(_, m) {
            if (currentplace >= len) {
                good = false;break;
            }
            int nxtval;
            if (carr[currentplace] >= adig || carr[currentplace] == 0) {
                nxtval = carr[currentplace];
                currentplace++;
            } else {
                if (currentplace + 1 >= len) {
                    good = false;break;
                }
                nxtval = carr[currentplace] *10 + carr[currentplace + 1];
                currentplace+=2;
            }
            if (nxtval%adig!= 0) {
                good = false;break;
            }
            possibleB.push_back(nxtval/adig);
        }
       // cout<<adig<<"..\n";
       // printarr(possibleB);
       // cout<<good<<"..\n";
        if (!good) continue;
        vi curA = {adig};
        REP(i, n-1) {
            bool found = false;
            REP(ndig, 10) {
                int nxtidx = getseq(ndig, possibleB, carr, currentplace);
                if (nxtidx != -1) {
                    found = true;
                    currentplace = nxtidx;
                    curA.push_back(ndig);break;
                }
            }
            if (!found) {
                break;
            }
        }
      //  printarr(curA);
        if (curA.size() == n && currentplace == len) {
            for (auto x: curA) {
                cout<<x;
            }cout<<" ";
            for (auto x: possibleB) {
                cout<<x;
            }
            cout<<"\n";return;
        }
    }
    cout<<"Impossible\n";

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while (t--) {
        solve();
    }
}

详细

Test #1:

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

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: 5312kb

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