oj.uz

Submission #507655

# Submission time Handle Problem Language Result Execution time Memory
507655 2022-01-12T22:47:22 Z ETK Weird Numeral System (CCO21_day1problem2) C++14
8 / 25
 2500 ms 1564 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];
map <ll,bool> mp;
vector <int> ans;
bool dp(ll x){
    if(mp.count(x))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 0 ms 204 KB OK
2 Correct 0 ms 204 KB OK
3 Correct 1 ms 204 KB OK
4 Correct 1 ms 300 KB OK
5 Correct 1 ms 204 KB OK
6 Correct 1 ms 300 KB OK
7 Correct 0 ms 296 KB OK
8 Correct 0 ms 204 KB OK

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB OK
2 Correct 0 ms 204 KB OK
3 Correct 1 ms 204 KB OK
4 Correct 1 ms 300 KB OK
5 Correct 1 ms 204 KB OK
6 Correct 1 ms 300 KB OK
7 Correct 0 ms 296 KB OK
8 Correct 0 ms 204 KB OK
9 Correct 1 ms 332 KB OK
10 Correct 1 ms 204 KB OK
11 Correct 0 ms 204 KB OK
12 Correct 0 ms 292 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 0 ms 204 KB OK
18 Correct 1 ms 332 KB OK
19 Correct 1 ms 204 KB OK
20 Correct 1 ms 204 KB OK
21 Correct 88 ms 1516 KB OK
22 Correct 602 ms 1468 KB OK
23 Execution timed out 2562 ms 1564 KB Time limit exceeded
24 Halted 0 ms 0 KB -