代码

#include "router.h"

class RoutingTableEntry_z
{
public:
    unsigned addr;
    unsigned char len;
    unsigned nexthop;
    unsigned mask;
    void set(RoutingTableEntry fr)
    {
        len = fr.len;
        mask = -1;
        mask >>= (32 - len);
        mask <<= len;
        nexthop = fr.nexthop;
        addr = 0;
        for (int i = 0; i < 4; i++)
        {
            addr <<= 8;
            addr |= (fr.addr >> (i*8)) & 255;
        }
    }
    bool check(unsigned checkaddr)
    {
        if (addr & mask == checkaddr & mask)
            return true;
        return false;
    }
}table[827090];

int N;
unsigned Reverse(unsigned addr)
{
    unsigned ret = 0;
    for (int i = 0; i < 4; i++)
    {
        ret <<= 8;
        ret |= (addr >> (i*8)) & 255;
    }
    return ret;
}

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

unsigned query(unsigned addr) {
    addr = Reverse(addr);
    int len = -1;
    unsigned nexthop = 0;
    for (int i = 0; i < N; i++)
    {
        if (table[i].check(addr) && table[i].len > len)
        {
            len = table[i].len;
            nexthop = table[i].nexthop;
        }
    }
    // 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;
    return nexthop;
}

评测结果