oj.uz

Submission #732587

# Submission time Handle Problem Language Result Execution time Memory
732587 2023-04-29T06:23:49 Z Programmer123 Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 996 ms 5140 KB 
#include <bits/stdc++.h>
#define int long long int
#define IMPOSSIBLE 10000
std::unordered_set<int> digits;
int K, M;
std::unordered_map<int, int> answer;
int dp(int num) {
    if (answer.count(num)) return answer[num];
    if (digits.count(num)) {
        answer[num] = num;
        return num;
    }
    answer[num] = IMPOSSIBLE;
    for (auto digit: digits) {
        int newNum = num - digit;
        if (newNum % K != 0) continue;
        if (dp(newNum / K) == IMPOSSIBLE) continue;
        answer[num] = digit;
        return digit;
    }
    return IMPOSSIBLE;
}
signed main() {
    int Q, D;
    std::cin >> K >> Q >> D >> M;
    for (int i = 0; i < D; ++i) {
        int a;
        std::cin >> a;
        digits.insert(a);
    }
    for (int _ = 0; _ < Q; ++_) {
        int number;
        std::cin >> number;
        if (dp(number) != IMPOSSIBLE) {
            std::stack<int> result;
            result.push(dp(number));
            number = (number - dp(number)) / K;
            while (number) {
                int digit = dp(number);
                result.push(digit);
                number -= digit;
                number /= K;
            }
            while (!result.empty()) {
                std::cout << result.top() << (result.size() > 1 ? " " : "");
                result.pop();
            }
            std::cout << std::endl;
        } else {
            std::cout << "IMPOSSIBLE" << std::endl;
        }
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB OK
2 Correct 0 ms 212 KB OK
3 Correct 0 ms 212 KB OK
4 Correct 0 ms 212 KB OK
5 Correct 0 ms 212 KB OK
6 Correct 1 ms 212 KB OK
7 Correct 0 ms 212 KB OK
8 Correct 1 ms 212 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB OK
2 Correct 0 ms 212 KB OK
3 Correct 0 ms 212 KB OK
4 Correct 0 ms 212 KB OK
5 Correct 0 ms 212 KB OK
6 Correct 1 ms 212 KB OK
7 Correct 0 ms 212 KB OK
8 Correct 1 ms 212 KB OK
9 Correct 1 ms 340 KB OK
10 Correct 0 ms 212 KB OK
11 Correct 1 ms 212 KB OK
12 Correct 0 ms 212 KB OK
13 Correct 1 ms 212 KB OK
14 Correct 1 ms 212 KB OK
15 Correct 1 ms 212 KB OK
16 Correct 1 ms 212 KB OK
17 Correct 1 ms 340 KB OK
18 Correct 1 ms 212 KB OK
19 Correct 1 ms 340 KB OK
20 Correct 0 ms 212 KB OK
21 Correct 28 ms 1144 KB OK
22 Correct 203 ms 1060 KB OK
23 Correct 996 ms 5140 KB OK
24 Correct 390 ms 1896 KB OK
25 Correct 1 ms 212 KB OK
26 Correct 1 ms 212 KB OK
27 Correct 0 ms 212 KB OK
28 Correct 0 ms 304 KB OK