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
93
94
95
96
|
// todo: pazi na težave s prvim elementom
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define S 1600002
#define ABS(x) ((x) > 0 ? (x) : -(x))
int main (void) {
int ukazov = 0;
char buf[S];
fgets(buf, S, stdin);
int n = strtol(buf, NULL, 10);
fgets(buf, S, stdin);
char * cp = buf;
int * arr = calloc(n, sizeof *arr);
int * repr = calloc(10e6, sizeof *arr);
int najrepr = 0;
int najreprval = 0;
for (int i = 0; i < n; i++) {
arr[i] = strtol(cp, &cp, 10);
if (++repr[arr[i]] > najreprval) {
najreprval = repr[arr[i]];
najrepr = arr[i];
}
cp++;
}
free(repr);
int razd_od_centr = INT_MAX;
int center = 0;
if (najreprval == 1) {
najrepr = arr[n/2];
center = n/2;
}
for (int i = 0; i < n; i++) {
if (arr[i] == najrepr && ABS(n/2-i) < razd_od_centr) {
razd_od_centr = ABS(n/2-i);
center = i;
}
}
if (najreprval == 1) {
center = n/2;
}
#ifndef EVAL
fprintf(stderr, "najrepr je število %d, ki ima toliko pojavitev: %d\n", najrepr, najreprval);
#endif
int levo = 0;
int desno = n-1;
s:
while (arr[levo] == najrepr) {
if (levo == n-1)
goto k;
levo++;
}
while (arr[desno] == najrepr) {
if (desno == 0)
goto k;
desno--;
}
if (levo == desno) {
ukazov++;
goto k;
}
if (center > levo && center < desno) {
ukazov++;
arr[levo] = najrepr;
arr[desno] = najrepr;
#ifndef EVAL
fprintf(stderr, "(%d, %d, %d) .. cached center\n", levo, center, desno);
#endif
goto s;
}
center = 0;
for (int i = levo+1; i < desno; i++) {
if (arr[i] == najrepr) {
center = i;
arr[levo] = najrepr;
arr[desno] = najrepr;
ukazov++;
#ifndef EVAL
fprintf(stderr, "(%d, %d, %d) .. našel center, en ukaz\n", levo, center, desno);
#endif
goto s;
}
}
if (center == 0) {
ukazov += 2;
arr[levo] = najrepr;
arr[desno] = najrepr;
arr[(center = levo+(desno-levo)/2)] = najrepr;
#ifndef EVAL
fprintf(stderr, "(%d, %d, %d) .. ni bilo centra, dva ukaza\n", levo, center, desno);
#endif
goto s;
}
k:
printf("%d\n", ukazov);
}
|
