oj.uz

Submission #1103675

# Submission time Handle Problem Language Result Execution time Memory
1103675 2024-10-21T14:06:38 Z BuzzyBeez Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 313 ms 4996 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 336 KB OK
2 Correct 1 ms 592 KB OK
3 Correct 1 ms 336 KB OK
4 Correct 1 ms 336 KB OK
5 Correct 1 ms 336 KB OK
6 Correct 1 ms 336 KB OK
7 Correct 1 ms 336 KB OK
8 Correct 1 ms 336 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB OK
2 Correct 1 ms 592 KB OK
3 Correct 1 ms 336 KB OK
4 Correct 1 ms 336 KB OK
5 Correct 1 ms 336 KB OK
6 Correct 1 ms 336 KB OK
7 Correct 1 ms 336 KB OK
8 Correct 1 ms 336 KB OK
9 Correct 1 ms 336 KB OK
10 Correct 1 ms 336 KB OK
11 Correct 1 ms 336 KB OK
12 Correct 1 ms 336 KB OK
13 Correct 1 ms 336 KB OK
14 Correct 1 ms 336 KB OK
15 Correct 1 ms 336 KB OK
16 Correct 1 ms 336 KB OK
17 Correct 1 ms 336 KB OK
18 Correct 1 ms 336 KB OK
19 Correct 1 ms 336 KB OK
20 Correct 1 ms 456 KB OK
21 Correct 11 ms 1104 KB OK
22 Correct 64 ms 1072 KB OK
23 Correct 313 ms 4996 KB OK
24 Correct 127 ms 2000 KB OK
25 Correct 2 ms 336 KB OK
26 Correct 1 ms 336 KB OK
27 Correct 1 ms 336 KB OK
28 Correct 1 ms 592 KB OK