QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#496996#6129. Magic Multiplicationucup-team1198#AC ✓9ms5300kbC++202.2kb2024-07-28 17:52:402024-07-28 17:52:41

Judging History

你现在查看的是最新测评结果

  • [2024-07-28 17:52:41]
  • 评测
  • 测评结果:AC
  • 用时:9ms
  • 内存:5300kb
  • [2024-07-28 17:52:40]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

void solve() {
  int n, m;
  cin >> n >> m;
  string s;
  cin >> s;
  auto move_digit = [&](int i, int d) {
    if (i == s.size() || i == -1)
      return -1;
    if (s[i] != '0' + d)
      return -1;
    return i + 1;
  };
  auto move_num = [&](int i, int x) {
    if (x < 10)
      return move_digit(i, x);
    return move_digit(move_digit(i, x / 10), x % 10);
  };
  auto move_div = [&](int i, int a) {
    if (i == s.size() || i == -1)
      return make_pair(-1, -1);
    int k = s[i] - '0';
    if (k != 0 && k < a) {
      ++i;
      if (i == s.size())
        return make_pair(-1, -1);
      k = k * 10 + s[i] - '0';
    }
    if (k % a != 0)
      return make_pair(-1, -1);
    return make_pair(i + 1, k / a);
  };
  vector<int> a(n);
  vector<int> b(m);
  for (a[0] = 1; a[0] < 10; ++a[0]) {
    int cur_i = 0;
    bool ok = true;
    for (int j = 0; ok && j < m; ++j) {
      auto tmp = move_div(cur_i, a[0]);
      if (tmp.first == -1) {
        ok = false;
        break;
      }
      b[j] = tmp.second;
      cur_i = tmp.first;
    }
    if (!ok || b[0] == 0)
      continue;
    for (int i = 1; ok && i < n; ++i) {
      auto tmp = move_div(cur_i, b[0]);
      if (tmp.first == -1) {
        ok = false;
        break;
      }
      a[i] = tmp.second;
      cur_i = tmp.first;
      for (int j = 1; ok && j < m; ++j) {
        cur_i = move_num(cur_i, b[j] * a[i]);
      }
      if (cur_i == -1) {
        ok = false;
        break;
      }
    }
    if (ok && cur_i == s.size()) {
      for (int i = 0; i < n; ++i)
        cout << a[i];
      cout << ' ';
      for (int j = 0; j < m; ++j)
        cout << b[j];
      cout << '\n';
      return;
    }
  }
  cout << "Impossible\n";
}


int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3608kb

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: 9ms
memory: 5300kb

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