#include #include struct mon { struct mon* next; int level; }; int cmp(const void* a, const void* b) { return (*(int*)a - *(int*)b); } int Base = 11; int Mask = 0; struct mon *List = 0; struct mon *ListPool = 0; struct mon *ListEnd = 0; void list_init(int N, int *A) { if (ListPool == 0) { qsort(A, N, sizeof(int), cmp); ListPool = (struct mon*)malloc(sizeof(struct mon)*N); ListEnd = ListPool+N; } List = ListPool; struct mon *l; for (l=List; lnext = l+1; l->level = *A; } List[N-1].next = 0; return; } struct mon *list_out(void) { struct mon *a = List; List = a->next; a->next = 0; return a; } void list_in(struct mon *a) { struct mon *l1 = 0; struct mon *l = List; while (l!=0) { if (a->level <= l->level) { break; } else { l1 = l; } l = l->next; } if (l1 == 0) { a->next = List; List = a; } else { a->next = l1->next; l1->next = a; } return; } int main() { int N; scanf("%d", &N); int *A = (int*)malloc(sizeof(int)*N*2); int *B = A+N; int *Ap; int *Aend = A+N; int *Bp; int *Bend = B+N; for (Ap=A; Ap>= 1; (*Bp) <<= Base; } Mask = (1 << Base)-1; int i; int min = N+1; int max = 0; int cnt; struct mon *a; list_init(N, A); for (i=0; ilevel += ((*Bp)+1); cnt = a->level & Mask; list_in(a); if (max < cnt) max = cnt; if (min <= max) goto NEXT; } for (Bp=B; Bplevel += ((*Bp)+1); cnt = a->level & Mask; list_in(a); if (max < cnt) max = cnt; if (min <= max) goto NEXT; } if (max < min) { min = max; } NEXT: max = 0; list_init(N, A); } printf("%d\n", min); return 0; }