Submission #852216

#	Time	Username	Problem	Language	Result	Execution time	Memory
852216		NaimSS	Weird Numeral System (CCO21_day1problem2)	C++14	25 / 25	795 ms	5248 KiB

Main

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(v) begin(v),end(v)
using namespace std;
typedef long long ll;

int k,d;

unordered_map<ll,int> dp, go;
set<int> A;
int a[2505];

int solve(ll num){
    if(dp.count(num))return dp[num];
    dp[num] = 0;
    rep(i,0,d){
        ll nv = num - a[i];
        if(nv%k)continue;
        if(solve(nv/k)){
            dp[num] = 1;
            go[num] = a[i];
            return 1;
        }
    }
    return dp[num] = 0;
}


int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int q,m;
    cin >> k >> q >> d >> m;

    rep(i,0,d)cin >> a[i],dp[a[i]] = 1, go[a[i]] = a[i];
    while(q--){
        ll N;
        cin >> N;
        if(solve(N)){
            vector<int> vals;
            while(N != 0 || vals.size()==0){
                int put = go[N];
                N = (N-put)/k;
                vals.push_back(put);
            }
            reverse(all(vals));
            rep(i,0,vals.size())cout<<vals[i]<<" \n"[i == vals.size()-1];
        }else{
            cout << "IMPOSSIBLE\n";
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:2:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define rep(i,a,b) for(int i=(a);i<(b);++i)
      |                                   ^
Main.cpp:46:13: note: in expansion of macro 'rep'
   46 |             rep(i,0,vals.size())cout<<vals[i]<<" \n"[i == vals.size()-1];
      |             ^~~
Main.cpp:46:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             rep(i,0,vals.size())cout<<vals[i]<<" \n"[i == vals.size()-1];
      |                                                      ~~^~~~~~~~~~~~~~~~

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