代码

#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;
const RoutingTableEntry *a;
void init(int n, int q, const RoutingTableEntry *tbl) {
    nn=n;a=tbl;
    for (int i = 0; i < n; i++) {
        ins(tbl + i);
    }
}
bool cmp(const RoutingTableEntry &u, const RoutingTableEntry &v){
    return u.addr<v.addr;
}
unsigned query(unsigned addr) {
    unsigned addr0=addr;
    addr = htonl(addr);

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

    return 0;
}

评测结果