QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#149579 | #6129. Magic Multiplication | pooty# | AC ✓ | 24ms | 5312kb | C++20 | 2.9kb | 2023-08-24 21:56:41 | 2023-08-24 21:56:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REPL(i,j, n) for (int i = (j); i < (n); i++)
typedef vector<int> vi;
typedef vector<vi> vvi;
int getseq(int val, vi &B, vi &reference, int starting) {
int mxs = reference.size();
int curidx = starting;
for (auto x: B) {
int gg = x*val;
if (gg < 10) {
if (curidx >= mxs) return -1;
if (reference[curidx] != gg) return -1;
curidx++;
} else {
int t1 = gg/10;
int t2 = gg%10;
if (curidx+1 >= mxs) return -1;
if (reference[curidx] != t1 || reference[curidx+1] != t2) return -1;
curidx+=2;
}
}
return curidx;
}
void printarr(vi arr) {
for (auto x: arr) {
cout<<x;
}cout<<"...\n";
}
void solve() {
int n,m;cin>>n>>m;
string cstr;
vi carr;
cin>>cstr;
for (auto x: cstr) {
carr.push_back(x - '0');
}
int len = cstr.size();
REPL(adig, 1, 10) {
int currentplace = 0;
bool good = true;
vi possibleB;
REP(_, m) {
if (currentplace >= len) {
good = false;break;
}
int nxtval;
if (carr[currentplace] >= adig || carr[currentplace] == 0) {
nxtval = carr[currentplace];
currentplace++;
} else {
if (currentplace + 1 >= len) {
good = false;break;
}
nxtval = carr[currentplace] *10 + carr[currentplace + 1];
currentplace+=2;
}
if (nxtval%adig!= 0) {
good = false;break;
}
possibleB.push_back(nxtval/adig);
}
// cout<<adig<<"..\n";
// printarr(possibleB);
// cout<<good<<"..\n";
if (!good) continue;
vi curA = {adig};
REP(i, n-1) {
bool found = false;
REP(ndig, 10) {
int nxtidx = getseq(ndig, possibleB, carr, currentplace);
if (nxtidx != -1) {
found = true;
currentplace = nxtidx;
curA.push_back(ndig);break;
}
}
if (!found) {
break;
}
}
// printarr(curA);
if (curA.size() == n && currentplace == len) {
for (auto x: curA) {
cout<<x;
}cout<<" ";
for (auto x: possibleB) {
cout<<x;
}
cout<<"\n";return;
}
}
cout<<"Impossible\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while (t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3452kb
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: 24ms
memory: 5312kb
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