代码

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

class RoutingTableEntry_z
{
public:
    unsigned addr;
    unsigned char len;
    unsigned nexthop;
    unsigned mask;
    void set(RoutingTableEntry fr)
    {
        len = fr.len;
        mask = 0xffffffffull << (32 - len);
        nexthop = fr.nexthop;
        addr = ntohl(fr.addr) & mask;
    }
    bool check(unsigned checkaddr)
    {
        if ((addr & mask) == (checkaddr & mask))
            return true;
        return false;
    }
    bool operator < (const RoutingTableEntry_z &a)
    {
        return addr < a.addr || addr == a.addr && len < a.len;
    }

}table[830000];

int N;

void init(int n, int q, const RoutingTableEntry *a) {
    N = n;
    for (int i = 0; i < n; i++)
        table[i].set(a[i]);
    sort(table, table + N);
}

unsigned query(unsigned addr) {
    addr = ntohl(addr);
    int ret = -1;
    for (int l = 0, r = N - 1; l <= r;)
    {
        int mid = (l + r) >> 1;
        if (table[mid].check(addr))
        {
            ret = mid;
            l = mid + 1;
        }
        else if (table[mid].addr < addr) l = mid + 1;
        else r = mid - 1;
    }
    return ret == -1 ? 0 : table[ret].nexthop;
}

评测结果