oj.uz

Submission #507656

# Submission time Handle Problem Language Result Execution time Memory
507656 2022-01-12T22:48:47 Z ETK Weird Numeral System (CCO21_day1problem2) C++14
25 / 25
 814 ms 1108 KB 
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=5005;
int K,q,D,M,a[N];
unordered_map <ll,bool> mp;
vector <int> ans;
bool dp(ll x){
    if(mp.find(x) != mp.end())return mp[x];
    mp[x] = 0;
    rep(i,1,D){
        if(x == a[i]){
            ans.pb(a[i]);
            return mp[x] = 1;
        }
        if((x-a[i]) % K == 0){
            if( (x-a[i]) / K != x && dp((x - a[i]) / K)){
                ans.pb(a[i]);
                return mp[x] = 1;
            }
        }
    }
    return mp[x];
}
int main(){
    K = read(),q = read(),D = read(),M = read();
    rep(i,1,D){
        a[i] = read();
    }
    while(q--){
        ll x = read();
        ans.clear();
        mp.clear();
        if(dp(x)){
            rep(i,0,sz(ans)-2)printf("%d ",ans[i]);
            printf("%d\n",ans.back());
        }else puts("IMPOSSIBLE");
    }
    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 0 ms 204 KB OK
4 Correct 0 ms 204 KB OK
5 Correct 0 ms 204 KB OK
6 Correct 1 ms 204 KB OK
7 Correct 0 ms 204 KB OK
8 Correct 0 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 0 ms 204 KB OK
4 Correct 0 ms 204 KB OK
5 Correct 0 ms 204 KB OK
6 Correct 1 ms 204 KB OK
7 Correct 0 ms 204 KB OK
8 Correct 0 ms 204 KB OK
9 Correct 1 ms 332 KB OK
10 Correct 0 ms 204 KB OK
11 Correct 1 ms 204 KB OK
12 Correct 0 ms 204 KB OK
13 Correct 1 ms 332 KB OK
14 Correct 1 ms 204 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 204 KB OK
20 Correct 0 ms 204 KB OK
21 Correct 23 ms 1048 KB OK
22 Correct 168 ms 1104 KB OK
23 Correct 814 ms 1108 KB OK
24 Correct 340 ms 1096 KB OK
25 Correct 1 ms 332 KB OK
26 Correct 1 ms 332 KB OK
27 Correct 0 ms 300 KB OK
28 Correct 0 ms 204 KB OK