Submission #1103702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103702		BuzzyBeez	Weird Numeral System (CCO21_day1problem2)	C++17	25 / 25	1835 ms	6216 KiB

Main

#include <bits/stdc++.h>
using namespace std;

map<long long, long long> memo;
vector<long long> arr;

long long k;
// bool attempt(long long R) {
	// if (par.count(R)) return (par[R] != inf);
	// par[R] = inf;
	// for (int x : arr) if (abs(R - x) % K == 0) 
		// if (R == x || attempt((R - x) / K)) {par[R] = x; return 1;}
	// return 0;
// }

bool solve(long long a){
    if(memo.count(a))return memo[a]!=LLONG_MAX;
    memo[a]=LLONG_MAX;
    for(auto x:arr){
        if((a-x)%k==0){
            if(a-x==0||solve((a-x)/k)){
                memo[a]=x;
                return true;
            }
        }
    }
    return false;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// int d, q, m; cin >> k >> q >> d >> m;
	// arr.resize(d);
	// for (int i = 0; i < d; ++i) cin >> arr[i];
	// long long a;
	int q,d,m;
    cin>>k>>q>>d>>m;
    arr.resize(d);
    for(int i=0;i<d;i++)cin>>arr[i];
    long long a;
	while (q--) {
		cin >> a; bool pass = solve(a);
		if (!pass) cout << "IMPOSSIBLE\n";
		else {
			vector<long long> fin; long long cur = a;
            while(1){
                fin.push_back(memo[cur]);
                cur=(cur-memo[cur])/k;
                if(cur==0)break;
            }
            reverse(fin.begin(),fin.end());
			for (int i = 0; i + 1 < fin.size(); ++i) cout << fin[i] << ' ';
			cout << fin.back();
			cout << '\n';
			// vector<long long> ans; long long x;
			// while (1) {
				// x = memo[a]; ans.push_back(x);
				// a = (a - x) / K;
				// if (a == 0) break;
			// }
			// reverse(ans.begin(), ans.end());
			// for (int i : ans) cout << i << ' ';
			// cout << '\n';
		}
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for (int i = 0; i + 1 < fin.size(); ++i) cout << fin[i] << ' ';
      |                    ~~~~~~^~~~~~~~~~~~

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