Source code for submission s964

Go to diff to previous submission

 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
	int position;
	int direction;
} ant_t;
 
enum {
	LEFT,
	RIGHT
};
 
int cmp(const void *v1, const void *v2) {
	ant_t *a1 = (ant_t*) v1;
	ant_t *a2 = (ant_t*) v2;
	return (a1->position - a2->position);
}
 
#define maximize(name, val) \
	{ if ((val) > name) name = (val); }
 
int main(void) {
	int i;
	int L, A;
 
	while(scanf(" %d %d", &L, &A) == 2) {
		ant_t ant;
		char c;
 
		ant_t *ants = (ant_t*)malloc(sizeof(ant_t) * A);
		for (i = 0; i < A; i++) {
			scanf(" %d %c", &ant.position, &c);
			ant.direction = (c == 'R') ? RIGHT : LEFT;
 
			ants[i] = ant;
		}
 
		qsort(ants, A, sizeof(ant_t), cmp);
 
		int lefts = 0;
		int rights = 0;
 
		int max_right = -1;
		int max_left = -1;
 
		for (int i = 0; i < A; i++) {
			ant = ants[i];
 
			if (ant.direction == RIGHT) {
				rights++;
 
				int len = L - ant.position;
				if (len > max_right) {
					max_right = len;
				}
			} else {
				lefts++;
 
				if (ant.position > max_left) {
					max_left = ant.position;
				}
			}
		}
 
		ant_t last_left;
		ant_t last_right;
 
		last_left.position = -1;
		last_right.position = -1;
		if (lefts != 0) {
			last_left = ants[lefts-1];
		}
		if (rights != 0) {
			last_right = ants[lefts];
		}
 
		if (max_right == max_left) {
			if (last_left.position > last_right.position) {
				int tmp = last_left.position;
				last_left.position = last_right.position;
				last_right.position = tmp;
			}
			printf("The last ant will fall down in %d seconds - started at %d and %d.\n", max_right, last_left.position, last_right.position);
		} else if (max_right > max_left) {
			printf("The last ant will fall down in %d seconds - started at %d.\n", max_right, last_right.position);
		} else {
			printf("The last ant will fall down in %d seconds - started at %d.\n", max_left, last_left.position);
		}
	}
 
	return 0;
}
 

Diff to submission s948

--- c4.s948.cteam091.ants.cpp.0.ants.cpp
+++ c4.s964.cteam091.ants.cpp.0.ants.cpp
@@ -8,34 +8,4 @@
 } ant_t;
 
-template<typename V>
-int bsearch(V *arr, int sz, int k) {
-        int min = 0;
-        int max = sz;
-        while (max > min) {
-                int mid = min + (max - min) / 2;
-                int cmp = key(arr[mid]) - k;
-                
-                if (cmp < 0) {
-                        min = mid + 1;
-                } else if (cmp > 0) {
-                        max = mid;
-                } else {
-                        return mid;
-                }
-        }
-        return min;
-}
-
-template<typename V>
-void sortInsert(V *arr, int sz, V val) {
-        int i = bsearch<V>(arr, sz, key(val));
-        while (i <= sz) {
-                V tmp1 = arr[i];
-                arr[i] = val;
-                val = tmp1;
-                i++;
-        }
-}
-
 enum {
         LEFT,
@@ -43,25 +13,8 @@
 };
 
-#define MAKE_STACK(name, sz, value_type) \
-        struct { size_t height; value_type *vals; } name; \
-        name.height = 0; \
-        name.vals = (value_type*) malloc(sizeof(value_type) * sz);
-
-#define push_sorted(name, val) \
-        (sortInsert(name.vals, name.height, val), name.height++, (void)0)
-
-#define push(name, val) \
-        (name.vals[name.height++] = (val))
-
-#define pop(name) \
-        (name.vals[--name.height])
-
-#define empty(name) \
-        (name.height == 0)
-
-
-
-int key(ant_t value) {
-        return -value.position;
+int cmp(const void *v1, const void *v2) {
+        ant_t *a1 = (ant_t*) v1;
+        ant_t *a2 = (ant_t*) v2;
+        return (a1->position - a2->position);
 }
 
@@ -77,13 +30,13 @@
                 char c;
                 
-                MAKE_STACK(ants, A, ant_t);
-                MAKE_STACK(ants2, A, ant_t);
-                
+                ant_t *ants = (ant_t*)malloc(sizeof(ant_t) * A);
                 for (i = 0; i < A; i++) {
                         scanf(" %d %c", &ant.position, &c);
                         ant.direction = (c == 'R') ? RIGHT : LEFT;
-                        push_sorted(ants, ant);
-                        push_sorted(ants2, ant);
+                        
+                        ants[i] = ant;
                 }
+
+                qsort(ants, A, sizeof(ant_t), cmp);
                 
                 int lefts = 0;
@@ -93,7 +46,6 @@
                 int max_left = -1;
                 
-                
-                while (!empty(ants)) {
-                        ant = pop(ants);
+                for (int i = 0; i < A; i++) {
+                        ant = ants[i];
                         
                         if (ant.direction == RIGHT) {
@@ -113,8 +65,4 @@
                 }
                 
-                for (int i = 0; i < lefts - 1; i++) {
-                        (void)pop(ants2);
-                }
-
                 ant_t last_left;
                 ant_t last_right;
@@ -123,8 +71,8 @@
                 last_right.position = -1;
                 if (lefts != 0) {
-                        last_left = pop(ants2);
+                        last_left = ants[lefts-1];
                 }
                 if (rights != 0) {
-                        last_right = pop(ants2);
+                        last_right = ants[lefts];
                 }