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
/*
 * ska.c
 *
 *  Created on: Nov 21, 2017
 *      Author: A.Mulawa
 */

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>

typedef unsigned char byte;

// 1000000 / 2 + 1 = 500001 possible bit's increment for 201718 * 1000000 values
// 201718 / 8 = 25214.75
// 500001 / 8 = 62500
//max is 87714.875 = (201718+500001) / 8 = (25215 + 62500)
const int RANGE = 131072; //131072 bytes / 1 Mbit / 0.125 MB
const int BIT = 8;

static bool get(byte a, byte pos)
{
    return (a >> pos) & 1;
}

static void set(byte *a, byte pos)
{
    *a |= 1 << pos;
}

static void reset(byte *a, byte pos)
{
    *a &= ~(1 << pos);
}

bool bitmapGet(byte *bitmap, int pos)
{
    return get(bitmap[pos / BIT], pos % BIT);
}

void bitmapSet(byte *bitmap, int pos)
{
    set(&bitmap[pos / BIT], pos % BIT);
}

void bitmapReset(byte *bitmap, int pos)
{
    reset(&bitmap[pos / BIT], pos % BIT);
}

int main(int argc, char **argv)
{
    byte* tabs = (byte*) malloc(RANGE);

    for (int i = 0; i < RANGE * 8; i++)
    {
        bitmapReset(tabs, i);
    }

    int n;
    int a;
    int mk = 0;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a);
        bool w;
        do
        {
            if (bitmapGet(tabs, a))
            {
                bitmapReset(tabs, a);
                a++;
                w = true;
            }
            else
            {
                bitmapSet(tabs, a);
                w = false;
            }
        } while (w);

        if (mk < a)
            mk = a;
    }

    printf("%d", mk);

    free(tabs);
}