joga_das_gomas.c

// By Pedro H. Lara Campos (RA 726578)
// Trabalho de PAA
// 2018-09-18

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define dprintf(...) //fprintf(stderr, __VA_ARGS__)

// Jogo Das Gomas que é sort, só que com enunciadinho
size_t swapc;

void msort(unsigned int *begin, unsigned int *middle, unsigned int *end, unsigned int *untouched) {
	if(end-begin == 1)
		return;
	else if(end-begin == 2 && *begin > *middle) {
		unsigned int aux = *begin;
		*begin = *middle;
		*middle = aux;
		swapc++;
		return;
	}

	msort(begin, &begin[(middle-begin)/2], middle, untouched);
	msort(middle, &middle[(end-middle)/2], end, untouched);

	memcpy(untouched, begin, (void*)end-(void*)begin);

	unsigned int *read_l=&untouched[0],
				 *read_r=untouched+(middle-begin),
				 *curr=&begin[0];
	
	unsigned int *read_m=read_r, *read_e=untouched+(end-begin);

	unsigned int swap_hack=middle-begin-(read_l-untouched);
	while(read_l < read_m  && read_r < read_e) {
		if(*read_l < *read_r) {
			*curr = *read_l;
			read_l++;
			swap_hack++;
		}else{
			swapc += swap_hack;
			*curr = *read_r;
			read_r++;
		}
		curr++;
	}
	if(read_l < read_m) memcpy(curr, read_l, (void*)read_m-(void*)read_l);
	else if(read_r < read_e) memcpy(curr, read_r, (void*)read_e-(void*)read_r);
}

int main() {
	size_t qty; 
	unsigned int *source, *end, *curr;

	while (scanf("%lu", &qty) == 1 && qty > 0) {
		source = (unsigned int*) malloc(sizeof(int)*qty);
		end = &source[qty];
		
		// READ THEM ALL
		dprintf("< ");
		for(curr=source; curr<end; curr++) {
			scanf("%u", curr);
			dprintf("%u ", *curr);
		}
		dprintf("#\n");

		// DO IT
		swapc = 0;
		unsigned int *untouched = (unsigned int*) malloc(sizeof(int)*qty);
		msort(source, &source[qty/2], &source[qty], untouched);
		free(untouched);
		
		// PRINT THEM ALL
		dprintf("> ");
		for(curr=source; curr<end; curr++)
			dprintf("%u ", *curr);
		dprintf("# %lu - WINNER: %s\n\n", swapc, (swapc % 2 ? "Jake" : "Finn"));
		
		if(swapc % 2) printf("Jake\n");
		else printf("Finn\n");

		free(source);
	}

	return 0;
}