代码

#include "router.h"
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <unordered_map>
#include <iostream>

std::unordered_map<uint32_t, RoutingTableEntry> map[33];

uint32_t big2small(uint32_t addr, int len) {
    auto result = 0;
    for (int i = 0; i < len; ++ i) {
        result = (result << 1) + (addr & 1);
        addr >>= 1;
    }
    return result;
}

void update(bool insert, RoutingTableEntry entry) {
    auto len = entry.len;
    // auto subnet = (len == 32) ?  0xffffffff :(1 << len) - 1;
    // auto refer = entry.addr & subnet;
    auto refer = big2small(entry.addr, len);
    if (insert) {
        if (map[len].count(refer) == 0) {
            map[len].insert(std::pair<uint32_t, RoutingTableEntry>(refer, entry));  
            // std::cout << "insert " << refer << " " << len << " " << std::endl;          
        } else {
            if (map[len][refer].addr == entry.addr && map[len][refer].len == entry.len) {
                map[len][refer] = entry;
            }
        }
    } else {
        if (map[len][refer].addr == entry.addr && map[len][refer].len == entry.len)
            map[len].erase(refer);
    }
}

void init(int n, int q, const RoutingTableEntry *a) {
	for (int i = 0; i < n; ++i) {
             update(true, a[i]);
        }
}

bool prefix_query(uint32_t addr, uint32_t *nexthop, uint32_t *if_index) {
    auto subnet = 0xffffffff;
    for (int i = 32; i >= 0; --i) {
        auto refer = big2small(addr, i);
        // if (i == 32) std::cout << "[32] " << refer << std::endl;
        if (map[i].count(refer) == 1) {
            // std::cout << "match " << i << " " << addr << std::endl;
            *nexthop = map[i][refer].nexthop;
            *if_index = map[i][refer].if_index;
            return true;
        } 
        subnet >>= 1;
    }
    return false;
}

unsigned query(unsigned addr) {
        unsigned a, b;
        if (prefix_query(addr, &a, &b)) return a;
	return 0;
}

评测结果