代码

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

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

const unsigned neg_pow[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
};

inline void ins(const RoutingTableEntry *e, int req_len) {
	if (e->len != req_len) return;
	unsigned addr = htonl(e->addr);
	for (int i = e->len; i >= 0; i--) {
		M[i][addr & neg_pow[32 - i]] = 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);
		}
	}
	
	if (M[0].count(0) == 0) {
		M[0][0] = 0;
	}
}

unsigned query(unsigned addr) {
	addr = htonl(addr);
	
	int l = 0, r = 32;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (M[mid].count(addr & neg_pow[32 - mid]) > 0) {
			l = mid;
		} else {
			r = mid - 1;
		}
	}
	
	return M[l][addr & neg_pow[32 - l]];
}

评测结果