QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#120126 | #6129. Magic Multiplication | hos_lyric | AC ✓ | 13ms | 5200kb | C++14 | 2.4kb | 2023-07-06 14:06:13 | 2023-07-06 14:06:14 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
int M, N;
int SLen;
char S[200'010];
vector<int> A, B;
bool solve(int a0) {
A.assign(M, 0);
B.assign(N, 0);
A[0] = a0;
int cur = 0;
for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) {
int val = 0;
for (int k = 0; ; ++k) {
if (k == 2) return false;
if (cur == SLen) return false;
(val *= 10) += (S[cur++] - '0');
if (k == 1 && val < 10) continue;
if (x == 0) {
B[y] = val / A[x];
} else if (y == 0) {
A[x] = val / B[y];
}
if (0 <= A[x] && A[x] <= 9 && 0 <= B[y] && B[y] <= 9 && val == A[x] * B[y]) {
break;
}
}
}
return (cur == SLen);
}
int main() {
for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
scanf("%d%d", &M, &N);
scanf("%s", S);
SLen = strlen(S);
for (int a0 = 1; a0 <= 9; ++a0) {
if (solve(a0)) {
for (int x = 0; x < M; ++x) putchar('0' + A[x]);
putchar(' ');
for (int y = 0; y < N; ++y) putchar('0' + B[y]);
puts("");
goto found;
}
}
puts("Impossible");
found:{}
}
#ifndef LOCAL
break;
#endif
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3680kb
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: 13ms
memory: 5200kb
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