QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#463237#6129. Magic Multiplicationjoelgun14TL 0ms3700kbC++142.7kb2024-07-04 16:18:032024-07-04 16:18:05

Judging History

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

  • [2024-07-04 16:18:05]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3700kb
  • [2024-07-04 16:18:03]
  • 提交

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

output:


result: