oj.uz

Submission #1103691

# Submission time Handle Problem Language Result Execution time Memory
1103691 2024-10-21T14:29:16 Z BuzzyBeez Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 1887 ms 6216 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;
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]);
        }
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB OK
2 Correct 1 ms 336 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 504 KB OK
2 Correct 1 ms 336 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 548 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 336 KB OK
21 Correct 57 ms 1464 KB OK
22 Correct 377 ms 1584 KB OK
23 Correct 1887 ms 6216 KB OK
24 Correct 763 ms 2780 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 336 KB OK