QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#463223#6129. Magic Multiplicationjoelgun14TL 0ms3624kbC++143.2kb2024-07-04 16:07:092024-07-04 16:07:09

Judging History

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

  • [2024-07-04 16:07:09]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3624kb
  • [2024-07-04 16:07:09]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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...

output:


result: