代码

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

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

void ins(const RoutingTableEntry *e) {
	unsigned addr = htonl(e->addr);
	if (e->len > 24) {
		for (int i = e->len; i >= 25; i--) {
			M25[addr] = e->nexthop;
		}
	} else if (e->len < 24) {
		for (int i = e->len; i >= 0; i--) {
			M0[addr] = e->nexthop;
		}
	} else {
		M24[addr] = e->nexthop;
	}
}

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

unsigned query(unsigned addr) {
	addr = htonl(addr);
	
	const unsigned suffices[32] = {
		~1, ~3, ~7, ~15, ~31, ~63, ~127, ~255,
		~511, ~1023, ~2047, ~4095, ~8191, ~16383,
		~32767, ~65535, ~131071, ~262143, ~524287,
		~1048575, ~2097151, ~4194303, ~8388607,
		~16777215, ~33554431, ~67108863, ~134217727,
		~268435455, ~536870911, ~1073741823, ~2147483647, 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]];
	}
}

评测结果