summaryrefslogtreecommitdiffstats
path: root/inf/zotksd/4.c
diff options
context:
space:
mode:
Diffstat (limited to 'inf/zotksd/4.c')
-rw-r--r--inf/zotksd/4.c96
1 files changed, 96 insertions, 0 deletions
diff --git a/inf/zotksd/4.c b/inf/zotksd/4.c
new file mode 100644
index 0000000..4c3113a
--- /dev/null
+++ b/inf/zotksd/4.c
@@ -0,0 +1,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);
+}