代码

#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] = {
		~1u, ~3u, ~7u, ~15u, ~31u, ~63u, ~127u, ~255u,
		~511u, ~1023u, ~2047u, ~4095u, ~8191u, ~16383u,
		~32767u, ~65535u, ~131071u, ~262143u, ~524287u,
		~1048575u, ~2097151u, ~4194303u, ~8388607u,
		~16777215u, ~33554431u, ~67108863u, ~134217727u,
		~268435455u, ~536870911u, ~1073741823u, ~2147483647u, 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] = {
		~1u, ~3u, ~7u, ~15u, ~31u, ~63u, ~127u, ~255u,
		~511u, ~1023u, ~2047u, ~4095u, ~8191u, ~16383u,
		~32767u, ~65535u, ~131071u, ~262143u, ~524287u,
		~1048575u, ~2097151u, ~4194303u, ~8388607u,
		~16777215u, ~33554431u, ~67108863u, ~134217727u,
		~268435455u, ~536870911u, ~1073741823u, ~2147483647u, 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]];
	}
}

评测结果