From 1f60c2ea7bf245486e104add6bafe5a34e0b83ae Mon Sep 17 00:00:00 2001
From: Raphael McSinyx <vn.mcsinyx@gmail.com>
Date: Wed, 28 Jun 2017 14:53:04 +0700
Subject: hsg/12/QG-2017/virus.c: Improve performance (still shitty though)

---
 12/QG-2017/virus.c          | 71 ++++++++++++++++++++++++++++++---------------
 12/QG-2017/virus_randinp.py |  9 ------
 2 files changed, 47 insertions(+), 33 deletions(-)
 delete mode 100755 12/QG-2017/virus_randinp.py

(limited to '12')

diff --git a/12/QG-2017/virus.c b/12/QG-2017/virus.c
index d4a56ba..add408c 100644
--- a/12/QG-2017/virus.c
+++ b/12/QG-2017/virus.c
@@ -1,22 +1,31 @@
 #include <stdio.h>
+#include <stdlib.h>
 #include <string.h>
 
-char difflim(char lim, char *s, short len)
+char T[3001], **mem;
+
+char difflim(char lim, short len, short beg)
 {
-	char i, count = 0;
+	char count = 0, *s, *z;
+	short i;
 
+	if (mem[len - 1][beg] >= 0)
+		return mem[len - 1][beg] <= lim;
+	s = T + beg;
+	z = s + len;
 	for (i = 0; i < len; i++)
-		if (s[i] != s[len + i] && ++count > lim)
-			return 0;
-	return 1;
+		if ((count += s[i] != z[i]) > 10)
+			break;
+	return (mem[len - 1][beg] = count) <= lim;
 }
 
 int main() {
 	FILE *f = fopen("VIRUS.INP", "r");
-	char i, n, level, T[3001], levels[10];
+	char i, n, level, *levels;
 	short m, j, k, len, lenpos, pos[3000], res[11] = {};
 
 	fscanf(f, "%hhd\n%s\n", &n, T);
+	levels = malloc(n);
 	for (i = 0; i < n; i++)
 		fscanf(f, "%hhd\n", levels + i);
 	fclose(f);
@@ -45,27 +54,41 @@ int main() {
 			}
 	}
 
-	f = fopen("VIRUS.OUT", "w");
-	for (i = 0; i < n; i++) {
-		level = levels[i];
-		if (level && !res[level]) {
-			if (level * 2 > m)
-				res[level] = m / 2;
-			else
-				res[level] = level;
-			for (j = 0; j < level; j++)
-				if (res[j] > res[level])
-					res[level] = res[j];
+	mem = malloc(m * sizeof(char *) / 2);
+	for (len = 0; len < m / 2; len++) {
+		mem[len] = malloc(m - len * 2);
+		for (j = 0; j < m - len * 2; j++)
+			mem[len][j] = -1;
+	}
 
-			for (len = m / 2; len > res[level]; len--)
-				for (j = 0; j <= m - len * 2; j++)
-					if (difflim(level, T + j, len)) {
-						res[level] = len;
-						break;
-					}
+	for (level = 1; level <= 10; level++) {
+		for (i = j = 0; i < n; i++)
+			if (levels[i] == level)
+				j++;
+		if (!j)
+			continue;
+
+		if (level * 2 > m) {
+			res[level] = m / 2;
+			continue;
 		}
-		fprintf(f, "%hd\n", res[level]);
+
+		res[level] = level;
+		for (j = 0; j < level; j++)
+			if (res[j] > res[level])
+				res[level] = res[j];
+
+		for (len = m / 2; len > res[level]; len--)
+			for (j = 0; j <= m - len * 2; j++)
+				if (difflim(level, len, j)) {
+					res[level] = len;
+					break;
+				}
 	}
+
+	f = fopen("VIRUS.OUT", "w");
+	for (i = 0; i < n; i++)
+		fprintf(f, "%hd\n", res[levels[i]]);
 	fclose(f);
 	return 0;
 }
diff --git a/12/QG-2017/virus_randinp.py b/12/QG-2017/virus_randinp.py
deleted file mode 100755
index 566e452..0000000
--- a/12/QG-2017/virus_randinp.py
+++ /dev/null
@@ -1,9 +0,0 @@
-#!/usr/bin/env python3
-import random
-import string
-
-with open('VIRUS.INP', 'w') as f:
-    f.write('10\n')
-    for _ in range(3000):
-        f.write(random.choice(string.ascii_lowercase))
-    f.write('\n0\n1\n2\n3\n5\n6\n7\n8\n9\n10\n')
-- 
cgit 1.4.1