QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#463237 | #6129. Magic Multiplication | joelgun14 | TL | 0ms | 3700kb | C++14 | 2.7kb | 2024-07-04 16:18:03 | 2024-07-04 16:18:05 |
Judging History
answer
// header file
#include <bits/stdc++.h>
// pragma
// 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;
int main() {
ios_base::sync_with_stdio(0); cin.tie(NULL);
int t;
cin >> t;
int mod[100][100], div[100][100], mul[100][100];
for(int i = 0; i < 100; ++i) {
for(int j = 0; j < 100; ++j) {
mul[i][j] = i * j;
if(j != 0)
mod[i][j] = i % j;
else
mod[i][j] = 0;
if(j != 0)
div[i][j] = i / j;
else
div[i][j] = 0;
}
}
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) {
int idx = 0;
vector<int> b;
b.reserve(m);
bool pos = 1;
while(idx < s.size() && b.size() < m) {
if(mod[a[idx]][i] == 0) {
b.pb(div[a[idx]][i]);
++idx;
}
else if(idx + 1 < s.size() && mod[mul[a[idx]][10] + a[idx + 1]][i] == 0 && div[(mul[a[idx]][10] + a[idx + 1])][i] < 10) {
b.pb(div[(mul[a[idx]][10] + a[idx + 1])][i]);
idx += 2;
}
else {
pos = 0;
break;
}
}
if(b.size() < m || !pos) {
continue;
}
vector<int> c = {i};
c.reserve(n);
while(c.size() < n && idx < s.size()) {
if(mod[a[idx]][b[0]] == 0) {
c.pb(div[a[idx]][b[0]]);
++idx;
}
else if(idx + 1 < s.size() && mod[(mul[a[idx]][10] + a[idx + 1])][b[0]] == 0 && div[(mul[a[idx]][10] + a[idx + 1])][b[0]] < 10) {
c.pb(div[(mul[a[idx]][10] + a[idx + 1])][b[0]]);
idx += 2;
}
for(int i = 1; i < b.size(); ++i) {
if(idx < s.size() && a[idx] == mul[b[i]][c.back()]) {
++idx;
}
else if(idx + 1 < s.size() && mul[a[idx]][10] + a[idx + 1] == mul[b[i]][c.back()]) {
idx += 2;
}
else {
pos = 0;
break;
}
}
if(!pos)
break;
}
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: 3700kb
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...