QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#120126#6129. Magic Multiplicationhos_lyricAC ✓13ms5200kbC++142.4kb2023-07-06 14:06:132023-07-06 14:06:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-06 14:06:14]
  • 评测
  • 测评结果:AC
  • 用时:13ms
  • 内存:5200kb
  • [2023-07-06 14:06:13]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int M, N;
int SLen;
char S[200'010];

vector<int> A, B;

bool solve(int a0) {
  A.assign(M, 0);
  B.assign(N, 0);
  A[0] = a0;
  int cur = 0;
  for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) {
    int val = 0;
    for (int k = 0; ; ++k) {
      if (k == 2) return false;
      if (cur == SLen) return false;
      (val *= 10) += (S[cur++] - '0');
      if (k == 1 && val < 10) continue;
      if (x == 0) {
        B[y] = val / A[x];
      } else if (y == 0) {
        A[x] = val / B[y];
      }
      if (0 <= A[x] && A[x] <= 9 && 0 <= B[y] && B[y] <= 9 && val == A[x] * B[y]) {
        break;
      }
    }
  }
  return (cur == SLen);
}

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d%d", &M, &N);
    scanf("%s", S);
    SLen = strlen(S);
    
    for (int a0 = 1; a0 <= 9; ++a0) {
      if (solve(a0)) {
        for (int x = 0; x < M; ++x) putchar('0' + A[x]);
        putchar(' ');
        for (int y = 0; y < N; ++y) putchar('0' + B[y]);
        puts("");
        goto found;
      }
    }
    puts("Impossible");
   found:{}
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3680kb

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: 13ms
memory: 5200kb

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