Submission #2200320

---

Source Code Expand

//#define NDEBUG
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <array>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

static constexpr double PI = 3.1415926535897932;

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;
using intl32 = std::int_least32_t;
using intl64 = std::int_least64_t;
using uintl32 = std::uint_least32_t;
using uintl64 = std::uint_least64_t;

template<typename T>
class RadixHeap32 {
	using uint32 = std::uint_fast32_t;
	using P = std::pair<uint32, T>;
	uint32 bsr(const uint32 x) {
		if (!x)
			return 0;
#ifdef __GNUC__
		return 32 - __builtin_clz(x);
#else
		uint32 t = 16;
		for (uint32 i = 3; ~i; --i) {
			if (x & ~(((uint32)1 << t) - 1)) {
				t += (uint32)1 << i;
			}
			else {
				t -= (uint32)1 << i;
			}
		}
		if (x & ~(((uint32)1 << t) - 1))
			++t;
		return t;
#endif
	}
	std::vector<P> v[33];
	uint32 last, size;

public:
	RadixHeap32() : last(0), size(0) {}
	P pop() {
		assert(size);
		--size;
		if (v[0].empty()) {
			uint32 i = 1;
			while (v[i].empty())
				++i;
			last = std::numeric_limits<uint32>::max();
			for (P &d : v[i])
				last = std::min(last, d.first);
			for (P &d : v[i])
				v[bsr(last ^ d.first)].push_back(d);
			v[i].clear();
		}
		P ret = v[0].back();
		v[0].pop_back();
		return ret;
	}
	void push(P x) {
		assert(last <= x.first);
		++size;
		v[bsr(x.first ^ last)].push_back(x);
	}
	bool empty() { return !size; }
};
struct edge {
	uint32 to;
	uint32 cost;
};

int main(void) {
	uint32 k;
	std::cin >> k;
	std::vector<std::vector<edge>> G(k);
	for (uint32 i = 0;i < k;++i) {
		G[i].push_back({ i * 10 % k,0 });
		G[i].push_back({ (i + 1) % k,1 });
	}
	RadixHeap32<uint32> Q;
	static constexpr uint32 INF = std::numeric_limits<uint32>::max();
	std::vector<uint32> d(k, INF);
	Q.push({ 1,1 });
	d[1] = 1;
	uint32 v, c;
	while (!Q.empty()) {
		std::tie(c, v) = Q.pop();
		if (d[v] < c) continue;
		for (const edge &e : G[v]) {
			if (c + e.cost < d[e.to]) {
				d[e.to] = c + e.cost;
				Q.push({ d[e.to],e.to });
			}
		}
	}
	std::cout << d[0] << "\n";
	return 0;
}

Submission Info

Judge Result