QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94209#6129. Magic Multiplicationinstallb#WA 24ms8940kbC++142.1kb2023-04-05 15:20:022023-04-05 15:20:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-05 15:20:04]
  • 评测
  • 测评结果:WA
  • 用时:24ms
  • 内存:8940kb
  • [2023-04-05 15:20:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005;

int ac,a[N],c[N];
string b;
int n,m;

pair <string,bool> calc(int x,int len){
    string ret = "";
    int cur = 1;
    for(int i = 1;i <= len;i ++){
        int now = a[cur];
        if(a[cur] < x && a[cur] != 0){
            now = a[cur] * 10 + a[cur + 1];
            cur ++;
        }
        if(now % x) return make_pair(ret,0);
        ret += (char)('0' + (now / x));
        cur ++;
    }
    return make_pair(ret,1);
}

pair <string,bool> calc2(string t){
    string ret = "";
    for(int i = 0;i < n;i ++) ret += '0';
    int cur = 1;
    for(int i = 0;i < n;i ++){
        for(int j = 0;j < m;j ++){
            int x = t[j] - '0',now = a[cur];
            if(a[cur] < x && a[cur] != 0){
                now = a[cur] * 10 + a[cur + 1];
                cur ++;
            }
            if((x == 0 && now != 0) || (x != 0 && now % x)) return make_pair(ret,0);
            if(j == 0) ret[i] = (now / x) + '0'; // x != 0
            else if(x != 0 && now / x != ret[i] - '0') return make_pair(ret,0);
            cur ++;
        }
    }
    return make_pair(ret,1);
}

bool chk(string &s,string &t){
    int cc = 0;
    for(int i = 0;i < n;i ++){
        for(int j = 0;j < m;j ++){
            int x = (s[i] - '0') * (t[j] - '0');
            if(x >= 10) c[++ cc] = 1;
            c[++ cc] = x % 10;
        }
    }
    if(cc != ac) return 0;
    for(int i = 1;i <= ac;i ++) if(c[i] != a[i]) return 0;
    return 1;
}

void solve(){
    cin >> n >> m;
    cin >> b;
    for(int i = 0;i < b.length();i ++) a[i + 1] = b[i] - '0';
    ac = b.length();
    for(int i = 1;i < 10;i ++){
        auto [t,tc] = calc(i,m);
        if(!tc) continue;
        auto [s,sc] = calc2(t);
        if(!sc) continue;
        if(chk(s,t)){
            cout << s << ' ' << t << '\n';
            return;
        }
    }
    cout << "Impossible" << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    int TC;
    cin >> TC;
    while(TC --){
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Wrong Answer
time: 24ms
memory: 8940kb

input:

1025
11 18
1461416814188088414188241035153540203545200202010354520510254921495628496328028281449632871435351535402035452002020103545205102500000000000000000000000000004000000063276372366381360363618638136918454921495628496328028281449632871435492149562849632802828144963287143514614168141880884141882...

output:

Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
26838140969 1
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
...

result:

wrong answer 2nd lines differ - expected: '3583 5', found: 'Impossible'