#include <stdio.h> #include <stdint.h> #define TAB_SIZE 6305 uint32_t t[TAB_SIZE]; void add_one(int pos) { if (t[pos] <= UINT32_MAX - 1) { t[pos]++; } else { t[pos]++; add_one(pos+1); } } void add(int a) { int ntor, dtor; uint32_t x; ntor = a / 32; dtor = a % 32; x = 1 << dtor; if (t[ntor] <= UINT32_MAX - x) { t[ntor] += x; } else { t[ntor] += x; add_one(ntor+1); } } int find_max_pos() { int i; for(i = TAB_SIZE-1; i >= 0; --i) { if (t[i] != 0) { return i; } } return 0; } unsigned int ulog2(uint32_t v) { static const unsigned MUL_DE_BRUIJN_BIT[] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; return MUL_DE_BRUIJN_BIT[(v * 0x07C4ACDDu) >> 27]; } int find_result() { int a, b; a = find_max_pos(); b = ulog2(t[a]); return 32*a + b; } int main() { int n, i; scanf("%d\n", &n); for(i = 0; i < n; ++i) { int tmp; scanf("%d", &tmp); add(tmp); } // printf("t[0]=%u\n", t[0]); // printf("t[1]=%u\n", t[1]); // printf("max pos=%d\n", find_max_pos()); printf("%d\n", find_result()); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | #include <stdio.h> #include <stdint.h> #define TAB_SIZE 6305 uint32_t t[TAB_SIZE]; void add_one(int pos) { if (t[pos] <= UINT32_MAX - 1) { t[pos]++; } else { t[pos]++; add_one(pos+1); } } void add(int a) { int ntor, dtor; uint32_t x; ntor = a / 32; dtor = a % 32; x = 1 << dtor; if (t[ntor] <= UINT32_MAX - x) { t[ntor] += x; } else { t[ntor] += x; add_one(ntor+1); } } int find_max_pos() { int i; for(i = TAB_SIZE-1; i >= 0; --i) { if (t[i] != 0) { return i; } } return 0; } unsigned int ulog2(uint32_t v) { static const unsigned MUL_DE_BRUIJN_BIT[] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; return MUL_DE_BRUIJN_BIT[(v * 0x07C4ACDDu) >> 27]; } int find_result() { int a, b; a = find_max_pos(); b = ulog2(t[a]); return 32*a + b; } int main() { int n, i; scanf("%d\n", &n); for(i = 0; i < n; ++i) { int tmp; scanf("%d", &tmp); add(tmp); } // printf("t[0]=%u\n", t[0]); // printf("t[1]=%u\n", t[1]); // printf("max pos=%d\n", find_max_pos()); printf("%d\n", find_result()); return 0; } |