oj.uz

Submission #852216

# Submission time Handle Problem Language Result Execution time Memory
852216 2023-09-21T12:37:58 Z NaimSS Weird Numeral System (CCO21_day1problem2) C++14
25 / 25
 795 ms 5248 KB 
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(v) begin(v),end(v)
using namespace std;
typedef long long ll;

int k,d;

unordered_map<ll,int> dp, go;
set<int> A;
int a[2505];

int solve(ll num){
    if(dp.count(num))return dp[num];
    dp[num] = 0;
    rep(i,0,d){
        ll nv = num - a[i];
        if(nv%k)continue;
        if(solve(nv/k)){
            dp[num] = 1;
            go[num] = a[i];
            return 1;
        }
    }
    return dp[num] = 0;
}


int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int q,m;
    cin >> k >> q >> d >> m;

    rep(i,0,d)cin >> a[i],dp[a[i]] = 1, go[a[i]] = a[i];
    while(q--){
        ll N;
        cin >> N;
        if(solve(N)){
            vector<int> vals;
            while(N != 0 || vals.size()==0){
                int put = go[N];
                N = (N-put)/k;
                vals.push_back(put);
            }
            reverse(all(vals));
            rep(i,0,vals.size())cout<<vals[i]<<" \n"[i == vals.size()-1];
        }else{
            cout << "IMPOSSIBLE\n";
        }
    }
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:2:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define rep(i,a,b) for(int i=(a);i<(b);++i)
      |                                   ^
Main.cpp:46:13: note: in expansion of macro 'rep'
   46 |             rep(i,0,vals.size())cout<<vals[i]<<" \n"[i == vals.size()-1];
      |             ^~~
Main.cpp:46:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             rep(i,0,vals.size())cout<<vals[i]<<" \n"[i == vals.size()-1];
      |                                                      ~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK
2 Correct 0 ms 348 KB OK
3 Correct 0 ms 348 KB OK
4 Correct 0 ms 348 KB OK
5 Correct 0 ms 348 KB OK
6 Correct 1 ms 348 KB OK
7 Correct 0 ms 348 KB OK
8 Correct 0 ms 348 KB OK
9 Correct 1 ms 348 KB OK
10 Correct 0 ms 348 KB OK
11 Correct 0 ms 348 KB OK
12 Correct 0 ms 348 KB OK
13 Correct 1 ms 344 KB OK
14 Correct 1 ms 348 KB OK
15 Correct 0 ms 348 KB OK
16 Correct 0 ms 348 KB OK
17 Correct 0 ms 348 KB OK
18 Correct 1 ms 600 KB OK
19 Correct 0 ms 348 KB OK
20 Correct 0 ms 348 KB OK
21 Correct 22 ms 1112 KB OK
22 Correct 166 ms 1420 KB OK
23 Correct 795 ms 5248 KB OK
24 Correct 323 ms 1896 KB OK
25 Correct 1 ms 348 KB OK
26 Correct 1 ms 348 KB OK
27 Correct 0 ms 348 KB OK
28 Correct 1 ms 348 KB OK