QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #91140 | #6129. Magic Multiplication | sycheng | AC ✓ | 438ms | 9996kb | C++20 | 5.5kb | 2023-03-27 14:48:35 | 2023-03-27 14:48:37 |
Judging History
answer
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <iostream>
#include <limits>
#include <numeric>
#include <type_traits>
#include <bitset>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;
#define rep(i,n,m) for(ll (i)=(n);(i)<(m);(i)++)
#define rrep(i,n,m) for(ll (i)=(n);(i)>(m);(i)--)
using ll = long long;
const ll mod = 998244353;
const ll inf = 1e10;
const ll INF = 1e18;
void pline(vector<int> lis){
rep(i,0,lis.size()){
printf ("%d",lis[i]);
if (i != lis.size()-1) printf(" ");
else printf("\n");
}
}
void pline(vector<ll> lis){
rep(i,0,lis.size()){
printf ("%lld",lis[i]);
if (i != lis.size()-1) printf(" ");
else printf("\n");
}
}
void pline(vector<pair<ll,ll>> lis){
rep(i,0,lis.size()){
printf ("%lld %lld,",lis[i].first,lis[i].second);
if (i != lis.size()-1) printf(" ");
else printf("\n");
}
}
int main(){
ll TT;
cin >> TT;
rep(loop,0,TT){
ll n,m;
cin >> n >> m;
string C;
cin >> C;
bool flag = false;
rep(af,1,10){
vector<ll> A(n,-1);
vector<ll> B(m,-1);
A[0] = af;
list<ll> q;
for (char cc : C){
q.push_back(cc - '0');
}
bool nok = true;
rep(bit,0,m){
ll bf = -1;
rep(nbf , 0 , 10){
ll mul = af * nbf;
if (mul >= 10){
if (q.size() < 2){
continue;
}
auto ptr = q.begin(); ptr++;
ll pick = q.front() * 10 + (*ptr);
if (pick == mul){
B[bit] = nbf;
bf = nbf;
q.pop_front(); q.pop_front();
break;
}
}else{
if (q.size() < 1){
continue;
}
ll pick = q.front();
if (pick == mul){
B[bit] = nbf;
bf = nbf;
q.pop_front();
break;
}
}
}
if (bf == -1){
nok = false;
break;
}
}
rep(bit,1,n){
ll af = -1;
rep(naf,0,10){
ll mul = naf * B[0];
if (mul >= 10){
if (q.size() < 2){
continue;
}
auto ptr = q.begin(); ptr++;
ll pick = q.front() * 10 + (*ptr);
if (pick == mul){
af = naf;
break;
}
}else{
if (q.size() < 1){
continue;
}
ll pick = q.front();
if (pick == mul){
af = naf;
break;
}
}
/*
}
if (q.empty()){
nok = false;
break;
}else if (q.front() == mul){
af = naf;
break;
}else if (mul >= 10 && q.front() == mul/10){
af = naf;
break;
}*/
}
if (af == -1){
nok = false;
break;
}
A[bit] = af;
rep(i,0,m){
ll mul = A[bit] * B[i];
if (q.empty()){
nok = false;
break;
}
if (mul < 10){
ll pick = q.front(); q.pop_front();
if (pick != mul){
nok = false;
break;
}
}else{
if (q.size() < 2){
nok = false;
break;
}
ll pick = q.front() * 10; q.pop_front();
pick += q.front(); q.pop_front();
if (pick != mul){
nok = false;
break;
}
}
}
}
if (!q.empty()) nok = false;
if (nok){
for (auto c : A) cout << c;
cout << " ";
for (auto c : B) cout << c;
cout << "\n";
flag = true;
break;
}
}
if (!flag){
cout << "Impossible" << "\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3440kb
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: 438ms
memory: 9996kb
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