HEADmaster

3 files changed, 160 insertions, 0 deletions

diff --git a/šola/aps1/dn/autocomplete/rešitev.cpp b/šola/aps1/dn/autocomplete/rešitev.cpp
new file mode 100644
index 0000000..0a5f42c
--- /dev/null
+++ b/šola/aps1/dn/autocomplete/rešitev.cpp
@@ -0,0 +1,143 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <stdbool.h>
+struct beseda {
+	char * niz;
+	long pomem;
+};
+static int compar_words (const void * aa, const void * bb) {
+	const char * a = ((const struct beseda *) aa)->niz;
+	const char * b = ((const struct beseda *) bb)->niz;
+	fprintf(stderr, "compar_words: %s, %s\n", a, b);
+	for (; *a && *b && *a == *b; a++, b++);
+	if (*a < *b)
+		return -1;
+	return *a > *b;
+}
+static int intlog(long n) {
+	int log = 1;
+	for (int dolžina = 1; dolžina < n; dolžina *= 2)
+		log++;
+	return log;
+}
+int main () {
+	long n;
+	if (scanf("%ld", &n) == EOF) {
+		perror("scanf n");
+		return 1;
+	}
+	struct beseda * s = (struct beseda *) malloc(n*sizeof *s);
+	if (!s) {
+		perror("malloc s");
+		return 1;
+	}
+	for (long i = 0; i < n; i++) {
+		if (scanf("%ms %ld", &(s[i].niz), &(s[i].pomem)) == EOF) {
+			perror("scanf");
+			return 1;
+		}
+	}
+	qsort(s, n, sizeof *s, compar_words);
+	for (long i = 0; i < n; i++) {
+		fprintf(stderr, "s[%ld].niz = \"%s\"; s[%ld].pomem = %ld;\n", i, s[i].niz, i, s[i].pomem);
+	}
+	int log = intlog(n);
+	// fprintf(stderr, "log: %d\n", log);
+	long * max = (long *) malloc((n*log)*sizeof *max);
+	if (!max) {
+		perror("malloc max");
+		return 1;
+	}
+	for (int i = 0; i < log; i++) {
+		for (long j = 0; j < n; j++) {
+			if (i == 0) {
+				max[i*n+j] = j;
+				continue;
+			}
+			if (j+(1 << (i-1)) >= n) {
+				max[i*n+j] = max[(i-1)*n+j];
+				continue;
+			}
+			max[i*n+j] = s[max[(i-1)*n+j+(1 << (i-1))]].pomem > s[max[(i-1)*n+j]].pomem ? max[(i-1)*n+j+(1 << (i-1))] : max[(i-1)*n+j];
+		}
+	}
+	long m;
+	if (scanf("%ld", &m) == EOF) {
+		perror("scanf m");
+		return 1;
+	}
+	long * o = (long *) malloc(m*sizeof *o);
+	for (long i = 0; i < m; i++) {
+		char buf[20000];
+		char bu2[20000];
+		struct beseda prefix = {
+			.niz = buf,
+			.pomem = 0
+		};
+		struct beseda nextprefix = {
+			.niz = bu2,
+			.pomem = 0
+		};
+		if (scanf("%s", buf) == EOF) {
+			perror("scanf buf");
+			return 1;
+		}
+		fprintf(stderr, "krneki: %s\n", buf);
+		strcpy(bu2, buf);
+		nextprefix.niz[strlen(nextprefix.niz)-1]++;
+		long l = 0, d = n;
+		while (l < d) {
+			long m = (l+d)/2;
+			switch (compar_words(&prefix, s+m)) {
+				case -1:
+					d = m-1;
+					break;
+				case 1:
+					l = m+1;
+					break;
+				case 0:
+					l = d = m;
+					break;
+				default:
+					assert(false);
+			}
+		}
+		long start = l;
+		fprintf(stderr, "found start = %ld;\n", start);
+		l = 0, d = n;
+		while (l < d) {
+			long m = (l+d)/2;
+			switch (compar_words(&nextprefix, s+m)) {
+				case -1:
+					d = m-1;
+					break;
+				case 1:
+					l = m+1;
+					break;
+				case 0:
+					l = d = m;
+					break;
+				default:
+					assert(false);
+			}
+		}
+		long end = l;
+		fprintf(stderr, "found end = %ld;\n", end);
+		int winsizelog = intlog(end-start)-1;
+		o[i] = 0;
+		if (winsizelog)
+			o[i] = s[max[winsizelog*n+(end-(1 << (winsizelog-1)))]].pomem > s[max[winsizelog*n+start]].pomem ? max[winsizelog*n+start] : max[winsizelog*n+(end-(1 << (winsizelog-1)))];
+		fprintf(stderr, "o[%ld] = %ld;\n", i, o[i]);
+	}
+	bool devica = true;
+	for (long i = 0; i < m; i++) {
+		if (devica)
+			devica = false;
+		else
+			putchar(' ');
+		printf("%ld", o[i]);
+	}
+	putchar('\n');
+}
diff --git a/šola/aps1/dn/autocomplete/test01.in b/šola/aps1/dn/autocomplete/test01.in
new file mode 100644
index 0000000..d654f34
--- /dev/null
+++ b/šola/aps1/dn/autocomplete/test01.in
@@ -0,0 +1,13 @@
+7
+algoritem 20
+drevo 1
+zaba 3
+zebra 10
+algebra 4
+alge 8
+program 5
+4
+alge
+x
+a
+zeb
diff --git a/šola/aps1/dn/autocomplete/test01.out b/šola/aps1/dn/autocomplete/test01.out
new file mode 100644
index 0000000..6d446c2
--- /dev/null
+++ b/šola/aps1/dn/autocomplete/test01.out
@@ -0,0 +1,4 @@
+6
+0
+1
+4