← Real problems

cco21p2

mediumgraphbfsstate-spacemathStatement on DMOJ

CP Lang

14 lines0.3 spec
// cco21p2 Weird Numeral System: write x as sum d_i k^i with every digit d_i from a given set.
// The lowest digit d must have d = x (mod k), and then x becomes (x - d) / k. Breadth-first
// search over those values finds a way down to 0; its arcs, read backwards, are the digits.
let (k, q, d, m) = read<(2..=1_000_000, 1..=5, 1..=5_001, 0..=2_500)>()
var by_residue: [0..k]List<Int> = []
for a in read<[d]-m..=m>():
    by_residue[a % k].push(a)
fn peel(x: Int) = by_residue[x % k].map(a => (to: (x - a) / k, digit: a))
for x in read<[q]Int>():
    let p = bfs(peel, from: [x], until: 0, hashed: true)
    if let arcs = p.arcs(0):
        print(arcs.rev.map(a => a.digit))
    else:
        print("IMPOSSIBLE")

Accepted C++

100 lines · 2.37 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

struct chash {
	uint64_t operator()(uint64_t x) const {
		x ^= x << 17;
		x ^= x >> 13;
		x ^= x << 19;
		x ^= x >> 16;
		return x;
	}
};

void solve() {
	int base, queries, n, m;
	cin >> base >> queries >> n >> m;
	auto md = [&](long x) -> int {
		x %= base;
		if (x < 0) {
			x += base;
		}
		return int(x);
	};
	int arr[n];
	for (auto& a : arr) {
		cin >> a;
	}
	vector<int> vals[base];
	for (auto& a : arr) {
		vals[md(a)].push_back(a);
	}
	while (queries--) {
		long x;
		cin >> x;
		__gnu_pbds::gp_hash_table<long, int, chash> from;
		vector<long> q = {x};
		for (int i = 0; i < 100; i++) {
			vector<long> nq;
			for (auto& a : q) {
				for (auto& b : vals[md(a)]) {
					long nxt = (a - b) / base;
					if (from.insert({nxt, b}).second) {
						nq.push_back(nxt);
					}
				}
			}
			if (from.find(0) != from.end()) {
				long u = 0;
				vector<int> ans;
				do {
					int cx = from[u];
					ans.push_back(cx);
					u = u * base + cx;
				} while (u != x);
				for (int j = 0; j < sz(ans); j++) {
					cout << ans[j] << " \n"[j == sz(ans) - 1];
				}
				goto loop;
			}
			swap(q, nq);
		}
		cout << "IMPOSSIBLE" << endl;
	loop:;
	}
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}