#include #include #include // Funkce pro načtení IP adresy nebo celého CIDR formátu. IPv4 adresa je 32 bitové // číslo, proto používáme uint32_t. Masku vracíme jen jako délku v uint8_t. // (obě funkce dostávají pointer na to, kam mají uložit výstupní hodnotu, a vrací // svůj návratový kód, tedy jestli uspěly nebo nastala chyba) int scan_ip(uint32_t *ip) { uint8_t a, b, c, d; // scanf řetězec "hhu" je 1 bajtové číslo bez znaménka if (scanf("%hhu.%hhu.%hhu.%hhu", &a, &b, &c, &d) < 4) { return -1; // nenačetli jsme všechna čtyři čísla } // Uložíme IP adresu pomocí bitových posunů do 32b čísla *ip = (a << 24UL) | (b << 16UL) | (c << 8UL) | d; return 0; } int scan_cidr(uint32_t *ip, uint8_t *bits) { if (scan_ip(ip) != 0) { return -1; } if (scanf("/%hhu", bits) != 1 || *bits > 32) { return -1; } return 0; } // Makro na vytažení konkrétního bitu z IPv4 adresy (počítáno zleva) #define IPv4BIT(x, pos) ((x) & (1UL << (31-pos))) //////////////////////////////////////////////////////////////////////////////// // Struktura pro vrchol stromu typedef struct node { char op; // A=allow, B=block, cokoliv jiného je "prázdno" struct node *left, *right; // odkazy na potomky } tnode; tnode *new_node(char op) { tnode *node = malloc(sizeof(tnode)); node->op = op; node->left = NULL; node->right = NULL; return node; } // Funkce přidávající/přepisující pravidla ve stromě void set_tree(tnode *node, uint32_t ip, uint8_t bits, uint8_t d, char op) { if (bits == d) { // Dorazili jsme do správné hloubky node->op = op; return; } else if (node->op == op) { // není potřeba nic dělat, tento podstrom je již nastavený správně return; } else if (node->op == 'A' || node->op == 'B') { // Musíme "rozhrnout" operaci do potomků if (node->left == NULL) node->left = new_node(node->op); else node->left->op = node->op; if (node->right == NULL) node->right = new_node(node->op); else node->right->op = node->op; node->op = ' '; // v tomto vrcholu nic není } // Rozhodneme se, kam pokračovat (0 doleva, 1 doprava) if (IPv4BIT(ip, d) == 0) set_tree(node->left, ip, bits, d+1, op); else set_tree(node->right, ip, bits, d+1, op); } int is_allowed(tnode *node, uint32_t ip, uint8_t d) { if (node->op == 'A') return 1; if (node->op == 'B') return 0; // Jinak se zeptáme na nižší úrovni (0 doleva, 1 doprava) if (IPv4BIT(ip, d) == 0) return is_allowed(node->left, ip, d+1); else return is_allowed(node->right, ip, d+1); } //////////////////////////////////////////////////////////////////////////////// int main() { // Inicializujeme strom (na začátku je celý rozsah blokovaný) tnode *root = new_node('B'); int N; scanf("%d", &N); char op; uint32_t ip; uint8_t bits; for (int i = 0; i < N; i++) { scanf(" %c", &op); if (op == 'A' || op == 'B') { if (scan_cidr(&ip, &bits) != 0) { exit(1); } set_tree(root, ip, bits, 0, op); } else if (op == 'Q') { if (scan_ip(&ip) != 0) { exit(1); } if (is_allowed(root, ip, 0)) printf("A\n"); else printf("N\n"); } } }