oj.uz

Submission #854258

# Submission time Handle Problem Language Result Execution time Memory
854258 2023-09-26T13:49:15 Z Lobo Swap Swap Sort (CCO21_day1problem1) C++17
0 / 25
 56 ms 11472 KB 
#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;

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

        int i = 0;
        while((i == 0 || 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 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 11472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -