oj.uz

Submission #411676

# Submission time Handle Problem Language Result Execution time Memory
411676 2021-05-25T17:52:56 Z Dormi Weird Numeral System (CCO21_day1problem2) C++14
25 / 25
 1106 ms 4920 KB 
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
int sz(const T &a){return int(a.size());}
ll k;
unordered_map<ll,ll> memo;
vector<ll> arr;
bool solve(ll a){
    if(memo.count(a))return memo[a]!=LLONG_MAX;
    memo[a]=LLONG_MAX;
    for(auto x:arr){
        if((a-x)%k==0){
            if(a-x==0||solve((a-x)/k)){
                memo[a]=x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int q,d,m;
    cin>>k>>q>>d>>m;
    arr.resize(d);
    for(int i=0;i<d;i++)cin>>arr[i];
    ll a;
    while(q--){
        cin>>a;
        bool te=solve(a);
        if(!te)printf("IMPOSSIBLE\n");
        else{
            ll cur=a;
            vector<ll> fin;
            while(1){
                fin.push_back(memo[cur]);
                cur=(cur-memo[cur])/k;
                if(cur==0)break;
            }
            reverse(fin.begin(),fin.end());
            for(int i=0;i<sz(fin);i++)printf("%lli%c",fin[i]," \n"[i==sz(fin)-1]);
        }
    }
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB OK
2 Correct 1 ms 204 KB OK
3 Correct 1 ms 204 KB OK
4 Correct 1 ms 204 KB OK
5 Correct 1 ms 204 KB OK
6 Correct 1 ms 204 KB OK
7 Correct 1 ms 204 KB OK
8 Correct 1 ms 204 KB OK
9 Correct 1 ms 332 KB OK
10 Correct 1 ms 332 KB OK
11 Correct 1 ms 204 KB OK
12 Correct 1 ms 236 KB OK
13 Correct 2 ms 332 KB OK
14 Correct 1 ms 332 KB OK
15 Correct 1 ms 204 KB OK
16 Correct 1 ms 204 KB OK
17 Correct 1 ms 204 KB OK
18 Correct 1 ms 332 KB OK
19 Correct 1 ms 332 KB OK
20 Correct 1 ms 204 KB OK
21 Correct 29 ms 1088 KB OK
22 Correct 226 ms 1064 KB OK
23 Correct 1106 ms 4920 KB OK
24 Correct 449 ms 1892 KB OK
25 Correct 1 ms 332 KB OK
26 Correct 1 ms 332 KB OK
27 Correct 1 ms 204 KB OK
28 Correct 1 ms 204 KB OK