代码

#include <unordered_map>
#include <arpa/inet.h>
#include "router.h"

std::unordered_map<unsigned, unsigned> M[33];

inline void ins(const RoutingTableEntry *e, int req_len) {
	if (e->len != req_len) return;
	
	unsigned addr = htonl(e->addr);
	
	const unsigned suffices[33] = {
		-1u, -2u, -4u, -8u, -16u, -32u, -64u, -128u,
		-256u, -512u, -1024u, -2048u, -4096u, -8192u, -16384u,
		-(1u << 15), -(1u << 16), -(1u << 17), -(1u << 18),
		-(1u << 19), -(1u << 20), -(1u << 21), -(1u << 22),
		-(1u << 23), -(1u << 24), -(1u << 25), -(1u << 26),
		-(1u << 27), -(1u << 28), -(1u << 29), -(1u << 30),
		-(1u << 31), 0
	};
	
	if (e->len > 24) {
		// 25..32 -> 1..8
		int len1 = e->len - 24;
		while (len1 <= 8) {
			M[24 + len1][addr] = e->nexthop;
			len1++;
		}
	} else if (e->len < 24) {
		// 0..23 -> 1..24
		int len1 = e->len + 1;
		while (len1 <= 24) {
			M[-1 + len1][addr] = e->nexthop;
			len1++;
		}
	} else {
		M[24][addr] = e->nexthop;
	}
}

void init(int n, int q, const RoutingTableEntry *tbl) {
	for (int len = 0; len <= 32; len++) {
		for (int i = 0; i < n; i++) {
			ins(tbl + i, len);
		}
	}
}

unsigned query(unsigned addr) {
	addr = htonl(addr);
	
	const unsigned suffices[33] = {
		-1u, -2u, -4u, -8u, -16u, -32u, -64u, -128u,
		-256u, -512u, -1024u, -2048u, -4096u, -8192u, -16384u,
		-(1u << 15), -(1u << 16), -(1u << 17), -(1u << 18),
		-(1u << 19), -(1u << 20), -(1u << 21), -(1u << 22),
		-(1u << 23), -(1u << 24), -(1u << 25), -(1u << 26),
		-(1u << 27), -(1u << 28), -(1u << 29), -(1u << 30),
		-(1u << 31), 0
	};
	
	if (M[25].count(addr & suffices[32 - 25]) > 0) {
		int l, r;
		l = 25, r = 32;
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			if (M[mid].count(addr & suffices[32 - mid]) > 0) {
				l = mid;
			} else {
				r = mid - 1;
			}
		}
		return M[l][addr & suffices[32 - l]];
	}
	
	addr &= suffices[32 - 24];
	if (M[24].count(addr) > 0) {
		return M[24][addr];
	} else {
		int l, r;
		l = 0, r = 23;
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			if (M[mid].count(addr & suffices[32 - mid]) > 0) {
				l = mid;
			} else {
				r = mid - 1;
			}
		}
		return M[l][addr & suffices[32 - l]];
	}
}

评测结果