oj.uz

Submission #732586

# Submission time Handle Problem Language Result Execution time Memory
732586 2023-04-29T06:23:10 Z Programmer123 Weird Numeral System (CCO21_day1problem2) C++17
8 / 25
 2500 ms 6216 KB 
#include <bits/stdc++.h>
#define int long long int
#define IMPOSSIBLE 10000
std::set<int> digits;
int K, M;
std::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 1 ms 212 KB OK
2 Correct 1 ms 212 KB OK
3 Correct 1 ms 212 KB OK
4 Correct 1 ms 212 KB OK
5 Correct 0 ms 212 KB OK
6 Correct 1 ms 224 KB OK
7 Correct 1 ms 212 KB OK
8 Correct 0 ms 212 KB OK

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB OK
2 Correct 1 ms 212 KB OK
3 Correct 1 ms 212 KB OK
4 Correct 1 ms 212 KB OK
5 Correct 0 ms 212 KB OK
6 Correct 1 ms 224 KB OK
7 Correct 1 ms 212 KB OK
8 Correct 0 ms 212 KB OK
9 Correct 1 ms 340 KB OK
10 Correct 1 ms 212 KB OK
11 Correct 1 ms 212 KB OK
12 Correct 1 ms 300 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 340 KB OK
19 Correct 1 ms 340 KB OK
20 Correct 1 ms 212 KB OK
21 Correct 91 ms 1612 KB OK
22 Correct 505 ms 1632 KB OK
23 Execution timed out 2514 ms 6216 KB Time limit exceeded
24 Halted 0 ms 0 KB -