Submission #854039

#	Time	Username	Problem	Language	Result	Execution time	Memory
854039		Lobo	Weird Numeral System (CCO21_day1problem2)	C++17	0 / 25	0 ms	344 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = -1;

void solve() {
    int k,q,d,m;
    cin >> k >> q >> d >> m;
    vector<int> a;
    for(int i = 1; i <= d; i++) {
        int x; cin >> x;
        a.pb(x);
    }

    sort(all(a));
    a.erase(unique(all(a)),a.end());

    while(q--) {
        int n; cin >> n;

        if(n == 0) {
            bool ok = false;
            for(auto x : a) if(x == 0) ok = true;

            if(ok) cout << 0 << endl;
            else cout << "IMPOSSIBLE" << endl;
            break;
        }

        vector<map<int,int>> dp(65);
        dp[0][n] = 0;

        int i = 0;
        while(dp[i].count(0) == 0 && dp[i].size() != 0) {
            for(auto X : dp[i]) {
                int nn = X.fr;
                for(auto x : a) {
                    if((x%k+k)%k == (nn%k+k)%k) {
                        dp[i+1][(nn-x)/k] = x;
                    }
                }
            }
            i++;
        }


        if(dp[i].count(0) != 0) {
            vector<int> ans;

            int nn = 0;
            while(i != 0) {
                ans.pb(dp[i][nn]);
                nn = nn*k+dp[i][nn];
                // cout << nn << endl;
                i--;
            }
            for(auto x : ans) cout << x << " ";
            cout << endl;
        }
        else {
            cout << "IMPOSSIBLE" << endl;
        }

        
    }
}
    
int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 17