QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91974#6129. Magic Multiplicationsycheng#AC ✓9ms3560kbC++143.1kb2023-03-30 02:06:112023-03-30 02:06:16

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-30 02:06:16]
  • 评测
  • 测评结果:AC
  • 用时:9ms
  • 内存:3560kb
  • [2023-03-30 02:06:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int n, m;
string s;
void work() {
    cin >> n >> m;
    cin >> s;
    int len = s.size();
    if(1LL * n * m > len){
        cout << "Impossible" << '\n';
        return;
    }
    int st = (n != 1);
    for(int i = st; i <= 9; i ++) {
        string B = ""; int now = 0;
        bool flag = 1;
        for(int j = 1; j <= m; j ++) {
            if(now == len){
                flag = 0;
                break;
            }
            int v = s[now] - '0'; ++now;
            if(i == 0 && v != 0){
                flag = 0;
                break;
            }
            if(v == 0){
                if(j == 1 && m != 1){
                    flag = 0;
                    break;
                }
                B += '0';
                continue;
            }
            if(now == len && v < i){
                flag = 0;
                break;
            }
            if(v < i) v = v * 10 + s[now] - '0', ++now;
            if(v % i != 0){
                flag = 0;
                break;
            }
            B += char(v / i + '0');
        }
        string A = "";
        A += char(i + '0');
        if(flag && n == 1){
            if(now == len){
                cout << A << ' ' << B << '\n';
                return;
            }
            continue;
        }
        if(flag && now < len){
            for(int j = 2; j <= n; ++j){
                int fow = -1;
                for(int t = 0; t < m; ++t){
                    if(now == len){
                        flag = 0;
                        break;
                    }
                    int x = B[t] - '0';
                    int v = s[now] - '0'; ++now;
                    if(x == 0 && v != 0){
                        flag = 0;
                        break;
                    }
                    if(v == 0){
                        if(fow != -1 && fow != 0 && x!= 0){
                            flag = 0;
                            break;
                        }
                        if(x != 0) fow = 0;
                        continue;
                    }
                    if(now == len && v < x){
                        flag = 0;
                        break;
                    }
                    if(v < x) v = v * 10 + s[now] - '0', ++now;
                    if(v % x != 0){
                        flag = 0;
                        break;
                    }
                    if(fow != -1 && fow != v / x){
                        flag = 0;
                        break;
                    }
                    fow = v / x;
                }
                if(!flag) break;
                if(fow == -1) fow = 0;
                A += char(fow + '0');
            }
            if(flag && now == len){
                cout << A << ' ' << B << '\n';
                return;
            }
        }
    }
    cout << "Impossible" << '\n';
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int Case;
    cin >> Case;
    while(Case --) work();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 9ms
memory: 3560kb

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