代码

#include "router.h"
#include <stdint.h>

/*
	Lulea Algorithm
	1. maptable (10.6KB + 128KB)
	2. TODO
*/

/*
	Maptable:
	Stores [0,678) x [0,16) -> [0,16) : 10.6KB
	Stores [0,2^16) -> [0,678) : 128KB
*/

const int MAPTABLE_MAX_SIZE = 678;

int maptable_size;
uint8_t maptable[MAPTABLE_MAX_SIZE][16];
uint16_t maptable_index_map[1 << 16];

/*
	Init maptable
	1. dfs all possible 16-bit tries
	2. calculate prefix sums
*/

inline void maptable_add(int vec) {
	maptable_index_map[vec] = maptable_size;
	int cnt = 0;
	for (int i = 0; i < 16; i++) {
		cnt += (vec >> i) & 1;
		maptable[maptable_size][i] = cnt;
	}
	++maptable_size;
}

inline bool maptable_element_check(int vec, int bits = 16) {
	if (vec == 1) return 1;
	if (bits == 1) return 0;
	bits >>= 1;
	int mask = (1 << bits) - 1;
	return maptable_element_check(vec & mask, bits)
		&& maptable_element_check(vec >> bits, bits);
}

void init_maptable() {
	maptable_size = 0;
	for (int i = 1; i < 1 << 16; i++) {
		if (maptable_element_check(i)) {
			maptable_add(i);
		}
	}
}

void init(int n, int q, const RoutingTableEntry *a) {
	init_maptable();
	assert(maptable_size == 677);
}

unsigned query(unsigned addr) {
	return 0;
}

评测结果