提交记录 14368


用户 题目 状态 得分 用时 内存 语言 代码长度
zhangzj router32. 测测你的路由器 Wrong Answer 50 542.282 ms 470044 KB C++ 3.28 KB
提交时间 评测时间
2020-09-24 19:36:32 2020-09-24 19:36:39
#include "router.h"
#include <cstring>
#include <arpa/inet.h>

long long nexthop_trie1[34000000];
long long nexthop_trie8[18000000];
int nodefr8to1[18000000];
long long *sub_trie[18000000];

unsigned Reverse(unsigned a, int len = 32)
{
    unsigned ret = 0;
    for (int cnt = len; cnt > 0; a >>= 1, cnt--)
    {
        ret <<= 1;
        ret |= a&1;
    }
    return ret;
}

void init(int n, int q, const RoutingTableEntry *a) {
    memset(nexthop_trie1, -1, sizeof(nexthop_trie1));
    memset(nexthop_trie8, -1, sizeof(nexthop_trie8));
    for (int i = 0; i < n; i++)
    {
        if (a[i].len > 24)
        {
            unsigned addr = a[i].addr;
            int cnt = 0;
            for (int l = 8; l <= 24; l += 8)
            {
                cnt = cnt << 8 | (addr & 255);
                cnt++;
                addr >>= 8;
            }
            if (sub_trie[cnt] == NULL)
            {
                sub_trie[cnt] = new long long[540];
                memset(sub_trie[cnt], -1, sizeof(long long) * 540);
            }
            int sub_cnt = 1;
            addr = Reverse(addr, 8);
            for (int l = 25; l <= a[i].len; l++)
            {
                sub_cnt = sub_cnt << 1 | (addr & 1);
                addr >>= 1;
            }
            sub_trie[cnt][sub_cnt] = a[i].nexthop;
        }
        if (a[i].len <= 24)
        {
            int cnt8 = 0;
            if (a[i].len % 8 == 0)
            {
                unsigned addr = a[i].addr;
                int cnt = 0;
                for (int l = 8; l <= a[i].len; l += 8)
                {
                    cnt = cnt << 8 | (addr & 255);
                    cnt++;
                    addr >>= 8;
                }
                nexthop_trie8[cnt] = a[i].nexthop;
                cnt8 = cnt;
            }
            unsigned addr = Reverse(ntohl(a[i].addr));
            int cnt = 1;
            for (int l = 1; l <= a[i].len; l++)
            {
                cnt = cnt << 1 | (addr & 1);
                addr >>= 1;
            }
            nexthop_trie1[cnt] = a[i].nexthop;
            if (a[i].len % 8 == 0)
                nodefr8to1[cnt8] = cnt;
        }
    }
}

unsigned query(unsigned addr_in) {
    unsigned addr = addr_in;
    unsigned ret = 0;
    int cnt = 0;
    int len = 0;
    int cnt8 = 0;
    if (nexthop_trie8[0] != -1)
        ret = nexthop_trie8[0];
    for (int l = 8; l <= 24; l += 8)
    {
        cnt = cnt << 8 | (addr & 255);
        cnt++;
        addr >>= 8;
        if (nexthop_trie8[cnt] != -1)
        {
            ret = nexthop_trie8[cnt];
            cnt8 = cnt;
            len = l;
        }
    }
    if (sub_trie[cnt] != NULL)
    {
        int sub_cnt = 1;
        for (int l = 7; l >= 0; l--)
        {
            sub_cnt = sub_cnt << 1 | ((addr >> l) & 1);
            if (sub_trie[cnt][sub_cnt] != -1)
            {
                len = 31 & (~l);
                ret = sub_trie[cnt][sub_cnt];
            }
        }
    }
    if (len < 24)
    {
        addr = ntohl(addr_in);
        cnt = nodefr8to1[cnt8];
        for (int l = 31 - len; l >= 8; l--)
        {
            cnt = cnt << 1 | ((addr >> l) & 1);
            if (len < (31 & (~l)) && nexthop_trie1[cnt] != -1)
            {
                ret = nexthop_trie1[cnt];
                len = 31 & (~l);
            }
        }
    }
    
    return ret;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #133.148 ms396 MB + 780 KBAcceptedScore: 25

Testcase #268.771 ms459 MB + 28 KBAcceptedScore: 25

Testcase #3309.209 ms459 MB + 28 KBWrong AnswerScore: 0

Testcase #4542.282 ms459 MB + 28 KBWrong AnswerScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2020-10-31 12:04:10 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用