QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#90948 | #6129. Magic Multiplication | ksunhokim | WA | 64ms | 4404kb | C++17 | 2.3kb | 2023-03-26 09:57:01 | 2023-03-26 09:57:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n,m;
cin >> n >> m;
string s;
cin >> s;
auto calc = [&](int a, vector<int>& B) -> bool {
int cur = 0;
B.assign(m, 0);
for (int i=0;i<m;i++){
if (cur >= s.size()) {
return false;
}
if ((s[cur] - '0') % a != 0) {
if (cur+1 >= s.size()) {
return false;
}
int d = (s[cur] - '0') * 10 + (s[cur+1]-'0');
if (d % a != 0) {
return false;
}
B[i] = d/a;
cur+=2;
} else {
int d = s[cur] - '0';
if (d % a != 0) {
return false;
}
B[i] = d/a;
cur++;
}
}
return true;
};
auto check = [&](int a, vector<int>& B, vector<int>& A) -> bool {
A.assign(n, 0);
A[0] = a;
int cur = 0;
for (int i=0;i<n;i++){
for (int j=0;j<m;j++){
if (cur >= s.size()) {
return false;
}
if (B[j] == 0) {
if (s[cur] != '0')
return false;
cur++;
continue;
}
if ((s[cur] - '0') % B[j] != 0) {
if (cur+1 >= s.size()) {
return false;
}
int d = (s[cur] - '0') * 10 + (s[cur+1]-'0');
if (d % B[j] != 0) return false;
if (j == 0 && i != 0) {
int nn = d/B[j];
if (nn > 9)
return false;
A[i] = nn;
} else if (A[i] != d/B[j]) {
return false;
}
cur+=2;
} else {
int d = s[cur] - '0';
if (j == 0 && i != 0) {
int nn = d/B[j];
if (nn > 9)
return false;
A[i] = nn;
} else if (A[i] != d/B[j]) {
return false;
}
cur++;
}
}
}
return cur == s.size();
};
for (int a=1;a<=9;a++){
vector<int> B,A;
if (calc(a, B) && check(a,B,A)) {
for (int i=0;i<n;i++){
cout << A[i];
}
cout << " ";
for (int i=0;i<m;i++){
cout << B[i];
}
cout << "\n";
return;
}
}
cout << "Impossible" << "\n";
}
int main() {
int t;
cin >> t;
while (t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3336kb
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: 64ms
memory: 4404kb
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:
wrong answer 119th lines differ - expected: '9 9691352', found: '3 27182739156'