summaryrefslogblamecommitdiffstats
path: root/inf/zotksd/4.c
blob: 4c3113a495500c4ecaf7c2db6ec16376267e319b (plain) (tree)































































































                                                                                                         
// 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);
}