QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#463223 | #6129. Magic Multiplication | joelgun14 | TL | 0ms | 3624kb | C++14 | 3.2kb | 2024-07-04 16:07:09 | 2024-07-04 16:07:09 |
Judging History
answer
// header file
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// pragma
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// macros
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int main() {
ios_base::sync_with_stdio(0); cin.tie(NULL);
int t;
cin >> t;
while(t--) {
int n, m;
string s;
cin >> n >> m >> s;
int a[s.size()];
for(int i = 0; i < s.size(); ++i)
a[i] = s[i] - '0';
bool ans = 0;
if(1ll * n * m > s.size()) {
cout << "Impossible" << endl;
continue;
}
for(int i = 1; i <= 9; ++i) {
// set a[0] to i
// find values of b
int idx = 0;
vector<int> b;
b.reserve(m);
bool pos = 1;
while(idx < s.size() && b.size() < m) {
if(a[idx] % i == 0) {
b.pb(a[idx] / i);
// cerr << a[idx] << endl;
++idx;
}
else if(idx + 1 < s.size() && (a[idx] * 10 + a[idx + 1]) % i == 0 && (a[idx] * 10 + a[idx + 1]) / i < 10) {
// cerr << a[idx] << " " << a[idx + 1] << endl;
b.pb(((a[idx] * 10 + a[idx + 1]) / i));
idx += 2;
}
else {
pos = 0;
break;
}
}
// cerr << "DEBUG B " << i << endl;
// for(auto x : b) {
// cerr << x << " ";
// }
// cerr << endl;
if(b.size() < m || !pos) {
continue;
}
vector<int> c = {i};
c.reserve(n);
while(c.size() < n && idx < s.size()) {
// cerr << "DEBUG " << i << " " << b[0] << " " << (a[idx] * 10 + a[idx + 1]) << endl;
if(a[idx] % b[0] == 0) {
c.pb(a[idx] / b[0]);
++idx;
}
else if(idx + 1 < s.size() && (a[idx] * 10 + a[idx + 1]) % b[0] == 0 && (a[idx] * 10 + a[idx + 1]) / b[0] < 10) {
c.pb((a[idx] * 10 + a[idx + 1]) / b[0]);
idx += 2;
}
for(int i = 1; i < b.size(); ++i) {
if(idx < s.size() && a[idx] == b[i] * c.back()) {
++idx;
}
else if(idx + 1 < s.size() && a[idx] * 10 + a[idx + 1] == b[i] * c.back()) {
idx += 2;
}
else {
pos = 0;
break;
}
}
if(!pos)
break;
}
// cerr << i << endl;
// for(auto x : c) {
// cerr << x << " ";
// }
// cerr << endl;
if(!pos || c.size() != n || b.size() != m || idx != s.size()) {
continue;
}
else {
for(auto x : c)
cout << x;
cout << " ";
for(auto x : b)
cout << x;
cout << endl;
ans = 1;
break;
}
}
if(!ans)
cout << "Impossible" << endl;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
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
Time Limit Exceeded
input:
1025 11 18 1461416814188088414188241035153540203545200202010354520510254921495628496328028281449632871435351535402035452002020103545205102500000000000000000000000000004000000063276372366381360363618638136918454921495628496328028281449632871435492149562849632802828144963287143514614168141880884141882...