代码

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

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

void ins(const RoutingTableEntry *e) {
    M[e->len][e->addr] = e->nexthop;
}

int nn;
RoutingTableEntry *a;
bool cmp(const RoutingTableEntry &u, const RoutingTableEntry &v){
    return u.addr<v.addr || u.addr==v.addr && u.len<v.len;
}
void init(int n, int q, const RoutingTableEntry *tbl) {
    nn=n;a=(RoutingTableEntry *)tbl;
    for (int i=0;i<n;i++){
        a[i].addr=htonl(a[i].addr);
    }
    std::sort(a,a+nn,cmp);
    for (int i = 0; i < n; i++) {
        ins(tbl + i);
    }
}
unsigned query(unsigned addr) {
    addr = htonl(addr);

    for (int i = 32; i >= 0; i--) {
        RoutingTableEntry tmp;
        tmp.addr=addr;
        tmp.len=i;
        int lo=std::lower_bound(a,a+nn,tmp,cmp)-a;
        int hi=std::upper_bound(a,a+nn,tmp,cmp)-a;
        for (int j=lo;j<nn;j++){
            if (a[j].addr==addr){
                if (a[j].len==i){
                    return a[j].nexthop;
                }
            }else{
                break;
            }
        }
        if (M[i].count(addr) > 0) {
            return M[i][addr];
        }
        addr &= ~(1u << (32 - i));
        unsigned addr0=~(1u<<((i-1)/8*8+7-(i-1)%8));
    }

    return 0;
}

评测结果