QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94209 | #6129. Magic Multiplication | installb# | WA | 24ms | 8940kb | C++14 | 2.1kb | 2023-04-05 15:20:02 | 2023-04-05 15:20:04 |
Judging History
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'