QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90948#6129. Magic MultiplicationksunhokimWA 64ms4404kbC++172.3kb2023-03-26 09:57:012023-03-26 09:57:03

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-26 09:57:03]
  • 评测
  • 测评结果:WA
  • 用时:64ms
  • 内存:4404kb
  • [2023-03-26 09:57:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
  int n,m;
  cin >> n >> m;
  string s;
  cin >> s;
  auto calc = [&](int a, vector<int>& B) -> bool {
    int cur = 0;
    B.assign(m, 0);
    for (int i=0;i<m;i++){
      if (cur >= s.size()) {
        return false;
      }
      if ((s[cur] - '0') % a != 0) {
        if (cur+1 >= s.size()) {
          return false;
        }
        int d = (s[cur] - '0') * 10 + (s[cur+1]-'0');
        if (d % a != 0) {
          return false;
        }
        B[i] = d/a;
        cur+=2;
      } else {
        int d = s[cur] - '0';
        if (d % a != 0) {
          return false;
        }
        B[i] = d/a;
        cur++;
      }
    }
    return true;
  };
  auto check = [&](int a, vector<int>& B, vector<int>& A) -> bool {
    A.assign(n, 0);
    A[0] = a;
    int cur = 0;
    for (int i=0;i<n;i++){
      for (int j=0;j<m;j++){
        if (cur >= s.size()) {
          return false;
        }
        if (B[j] == 0) {
          if (s[cur] != '0')
            return false;
          cur++;
          continue;
        }
        if ((s[cur] - '0') % B[j] != 0) {
          if (cur+1 >= s.size()) {
            return false;
          }
          int d = (s[cur] - '0') * 10 + (s[cur+1]-'0');
          if (d % B[j] != 0) return false;
          if (j == 0 && i != 0) {
            int nn =  d/B[j];
            if (nn > 9)
              return false;
            A[i] = nn;
          } else if (A[i] != d/B[j]) {
            return false;
          }
          cur+=2;
        } else {
          int d = s[cur] - '0';
          if (j == 0 && i != 0) {
            int nn =  d/B[j];
            if (nn > 9)
              return false;
            A[i] = nn;
          } else if (A[i] != d/B[j]) {
            return false;
          }
          cur++;
        }
      }
    }
    return cur == s.size();
  };
  for (int a=1;a<=9;a++){
    vector<int> B,A;
    if (calc(a, B) && check(a,B,A)) {
      for (int i=0;i<n;i++){
        cout << A[i];
      }
      cout << " ";
      for (int i=0;i<m;i++){
        cout << B[i];
      }
      cout << "\n";
      return;
    }
  }
  cout << "Impossible" << "\n";
}

int main() {
  int t;
  cin >> t;
  while (t--)
    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3336kb

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
Wrong Answer
time: 64ms
memory: 4404kb

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:

wrong answer 119th lines differ - expected: '9 9691352', found: '3 27182739156'