代码

#pragma GCC optimize("Ofast")
#include <arpa/inet.h>
#include <bits/stdc++.h>
#include "router.h"

const uint32_t TABLE_32_SIZE = 16384;
const uint32_t TABLE_24_SIZE = 65536;

uint32_t table_32_cnt = 0;
uint32_t table_24_cnt = 0;
uint32_t table_32[TABLE_32_SIZE][1 << 8] __attribute__((aligned(4096)));
uint32_t table_24[TABLE_24_SIZE][1 << 8] __attribute__((aligned(4096)));
uint32_t table_16[1 << 16] __attribute__((aligned(4096)));

inline void fill(uint32_t *a, int n, uint32_t val) {
	const uint32_t val4[4] = {val, val, val, val};
	while (n >= 4) {
		memcpy(a, val4, sizeof(val4));
		n -= 4;
		a += 4;
	}
	while (n) {
		a[0] = val;
		n--;
		a++;
	}
}

inline void fill_pow2(uint32_t *a, int k, uint32_t val) {
    fill(a, 1 << k, val);
    return;
    *a = val;
    for (int i = 0; i < k; i++) {
        memcpy(a + (1 << i), a, sizeof(*a) << i);
    }
}

void ins(uint32_t addr, int len, uint32_t nexthop) {
	if (len <= 16) {
		fill_pow2(table_16 + (addr >> 16), 16 - len, nexthop);
	} else if (len <= 24) {
		uint32_t &t16 = table_16[addr >> 16];
		addr = (addr & 65535u) >> 8;
		
		uint32_t *tmp;
		if (t16 < -TABLE_24_SIZE) {
			tmp = table_24[--table_24_cnt + TABLE_24_SIZE];
			fill(tmp, addr, t16);
			fill_pow2(tmp + addr, 24 - len, nexthop);
			fill(tmp + addr + (1u << (24 - len)), 256 - addr - (1u << (24 - len)), t16);
			t16 = table_24_cnt;
		} else {
			tmp = table_24[t16 + TABLE_24_SIZE];
			fill_pow2(tmp + addr, 24 - len, nexthop);
		}
	} else {
		uint32_t &t16 = table_16[addr >> 16];
		addr &= 65535u;
		
		uint32_t *tmp;
		if (t16 < -TABLE_24_SIZE) {
			tmp = table_24[--table_24_cnt + TABLE_24_SIZE];
			fill_pow2(tmp, 8, t16);
			t16 = table_24_cnt;
		} else {
			tmp = table_24[t16 + TABLE_24_SIZE];
		}
		
		uint32_t &t24 = tmp[addr >> 8];
		addr &= 255u;
		
		if (t24 < -TABLE_32_SIZE) {
			tmp = table_32[--table_32_cnt + TABLE_32_SIZE];
			fill(tmp, addr, t24);
			fill_pow2(tmp + addr, 32 - len, nexthop);
			fill(tmp + addr + (1u << (32 - len)), 256 - addr - (1u << (32 - len)), t24);
			t24 = table_32_cnt;
		} else {
			tmp = table_32[t24 + TABLE_32_SIZE];
			fill_pow2(tmp + addr, 32 - len, nexthop);
		}
	}
}

void init(int n, int q, const RoutingTableEntry *tbl) {
	for (int i = 0; i < n; i++) {
		ins(htonl(tbl[i].addr), tbl[i].len, tbl[i].nexthop);
	}
}

unsigned query(unsigned addr) {
	addr = htonl(addr);
	
	uint32_t tmp = table_16[addr >> 16];
	if (tmp >= -TABLE_24_SIZE) {
		addr &= 65535u;
		tmp = table_24[tmp + TABLE_24_SIZE][addr >> 8];
		if (tmp >= -TABLE_32_SIZE) {
			return table_32[tmp + TABLE_32_SIZE][addr & 255u];
		} else {
			return tmp;
		}
	} else {
		return tmp;
	}
}

评测结果