代码

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

std::unordered_map<unsigned, unsigned> M0, M24, M25;

inline void ins(const RoutingTableEntry *e, int req_len) {
	if (e->len != req_len) return;
	
	unsigned addr = htonl(e->addr);
	
	const unsigned suffices[33] = {
		0, -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) {
		for (int i = e->len; i >= 25; i--) {
			M25[addr & suffices[32 - i]] = e->nexthop;
		}
	} else if (e->len < 24) {
		for (int i = e->len; i >= 0; i--) {
			M0[addr & suffices[32 - i]] = e->nexthop;
		}
	} else {
		M24[addr] = e->nexthop;
	}
}

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

unsigned query(unsigned addr) {
	addr = htonl(addr);
	
	const unsigned suffices[33] = {
		0, -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 (M25.count(addr & suffices[32 - 25]) > 0) {
		int l, r;
		l = 25, r = 32;
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			if (M25.count(addr & suffices[32 - mid]) > 0) {
				l = mid;
			} else {
				r = mid - 1;
			}
		}
		return M25[addr & suffices[32 - l]];
	}
	
	addr &= suffices[32 - 24];
	if (M24.count(addr) > 0) {
		return M24[addr];
	} else {
		int l, r;
		l = 0, r = 23;
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			if (M0.count(addr & suffices[32 - mid]) > 0) {
				l = mid;
			} else {
				r = mid - 1;
			}
		}
		return M0[addr & suffices[32 - l]];
	}
}

评测结果