oj.uz

Submission #732720

# Submission time Handle Problem Language Result Execution time Memory
732720 2023-04-29T08:06:37 Z loctildore Weird Numeral System (CCO21_day1problem2) C++14
25 / 25
 1761 ms 1680 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
int k, q, d, m;
int a;
map<int, bool> done;
vector<int> vctr, ans;
bool dp(int x, bool top = false) {
    if (!x && !top) return true;
    if (done[x]) return false;
    done[x] = true;
    for (auto i : vctr) if ((x - i) % k == 0) {
        if (dp((x - i) / k)) {
            ans.push_back(i);
            return true;
        }
    }
    return false;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>k>>q>>d>>m;
    for (int i = 0; i < d; i++) {
        cin>>a;
        vctr.push_back(a);
    }
    for (int i = 0; i < q; i++) {
        done.clear();
        ans.clear();
        cin>>a;
        if (dp(a, true)) {
            for (int j = 0; j < ans.size(); j++) {
                cout<<ans[j];
                if (j != ans.size() - 1) cout<<' ';
            }
            cout<<endl;
        }
        else cout<<"IMPOSSIBLE"<<endl;
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:37:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for (int j = 0; j < ans.size(); j++) {
      |                             ~~^~~~~~~~~~~~
Main.cpp:39:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |                 if (j != ans.size() - 1) cout<<' ';
      |                     ~~^~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB OK
2 Correct 1 ms 212 KB OK
3 Correct 1 ms 324 KB OK
4 Correct 0 ms 324 KB OK
5 Correct 1 ms 212 KB OK
6 Correct 1 ms 212 KB OK
7 Correct 1 ms 316 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 1 ms 212 KB OK
3 Correct 1 ms 324 KB OK
4 Correct 0 ms 324 KB OK
5 Correct 1 ms 212 KB OK
6 Correct 1 ms 212 KB OK
7 Correct 1 ms 316 KB OK
8 Correct 1 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 212 KB OK
13 Correct 1 ms 340 KB OK
14 Correct 1 ms 316 KB OK
15 Correct 1 ms 340 KB OK
16 Correct 0 ms 212 KB OK
17 Correct 1 ms 340 KB OK
18 Correct 1 ms 320 KB OK
19 Correct 1 ms 340 KB OK
20 Correct 1 ms 212 KB OK
21 Correct 50 ms 1528 KB OK
22 Correct 367 ms 1680 KB OK
23 Correct 1761 ms 1644 KB OK
24 Correct 743 ms 1668 KB OK
25 Correct 2 ms 340 KB OK
26 Correct 2 ms 320 KB OK
27 Correct 1 ms 212 KB OK
28 Correct 1 ms 212 KB OK