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
/*  Potyczki Algorytmiczne 2021 Runda 1 B Oranżada (ORA)
    tsz
*/
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

#ifndef TSDEBUG
#define NDEBUG 1
#endif

#ifdef __MINGW32__
#define FMTU64 "I64u"
#define FMTI64 "I64d"
#else
#define FMTU64 "llu"
#define FMTI64 "lld"
#endif 

typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;

typedef uint64_t u64;

inline i32 Min(i32 a, i32 b)
{
    return a <= b ? a : b;
}

const i32 MaxLiczbaButelek = 500000;
const i32 MaxMarek = MaxLiczbaButelek;

const i32 DictSizeInWords = 7813;

u64 WidzianeMarki[DictSizeInWords] = { 0 };

int main()
{
    assert(MaxMarek <= DictSizeInWords * 64);

    i32 LiczbaButelek;
    i32 Cel;
    scanf("%d %d", &LiczbaButelek, &Cel);
    assert(1 <= LiczbaButelek);
    assert(LiczbaButelek <= MaxLiczbaButelek);
    assert(1 <= Cel);
    assert(Cel <= LiczbaButelek);

    i64 Sekundy = 0;
    i32 NastepnaPozycja = 0;
    for (i32 NumerButelki = 0;
         NumerButelki < LiczbaButelek && NastepnaPozycja < Cel;
         NumerButelki++
    ) {
        i32 Marka;
        scanf("%d", &Marka);
        assert(1 <= Marka);
        assert(Marka <= MaxMarek);
        i32 Indeks = Marka >> 6;
        u64 Maska = (u64)1 << (Marka & 0B00111111);
        u64 *Pos = &WidzianeMarki[Indeks];
        if ((*Pos & Maska) == 0) {
            *Pos = *Pos | Maska;
            Sekundy += NumerButelki - NastepnaPozycja;
            NastepnaPozycja++;
        }
    }

    if (NastepnaPozycja < Cel) {
        printf("-1\n");
    } else {
        printf("%" FMTI64 "\n", Sekundy);
    }

    return 0;
}