代码

#include "router.h"
#include <algorithm>
int nn;
RoutingTableEntry *b;
bool cmp(const RoutingTableEntry &x,const RoutingTableEntry &y){
return x.addr<y.addr || x.addr==y.addr && x.len<y.len;
}
void init(int n, int q, const RoutingTableEntry *a) {
	b=(RoutingTableEntry *)a;nn=n;
for (int i=0;i<nn;i++){
unsigned t;
if (b[i].len>0){
t=b[i].addr>>(32-b[i].len)<<(32-b[i].len);
}else{
t=0;
}
if (b[i].addr!=t){
b[i].addr=t;
}
}
std::sort(b,b+nn,cmp);
}

unsigned query(unsigned addr) {
for (int k=32;k>=0;k--){
int lo=nn-1,hi=-1;
while (lo-hi>1){
int mid=(lo+hi)/2;
if (b[mid].addr>=addr) lo=mid;
else hi=mid;
}
for (int i=lo;i<nn;i++){
if (b[i].addr==addr){
if (b[i].len==k) return b[i].nexthop;
}else{
break;
}
}
if (k<=1){
addr=0;
}else{
addr>>=(33-k);
addr<<=(33-k);
}
}
	return 0;
}

评测结果