Any ideas on how I could make this program run faster?
It's supposed to run under 0.5 seconds.
In some cases it does, in others it fails. [b]The task : [/b]
INPUT:
From the first line of the standard input read one integer (5 <= n <= 100000). Each of the following n lines will have one of the following two formats:
- 1 a - meaning that Mirko said aloud the number a, (0 <= a <= 65535).
- 2 k - meaning that Mirko asks what is the kth smallest number he has said so far. k will always be less or equal to the number of numbers Mirko has said aloud so far.
The total number of different number will not be bigger than 400, but some of the numbers can repeat!
OUTPUT:
To the standard output write one line for each of the 2 k inputs. Representing the kth smallest number at that moment.
Input:
7
1 0
1 1
1 5
2 1
2 3
1 2
2 3
Output:
0
5
2
My solution :
#include <stdio.h>
int main(){
unsigned short int * a;
unsigned int n,j,x,y;
int m=-1;
scanf("%u",&n);
a=new unsigned short int[n];
while (n>0){
n=n-1;
scanf("%u %u",&x,&y);
if (x==1){
m=m+1;
j=m;
a[j]=y;
while((j>0)&&(a[j]<a[j-1])){
y=a[j-1];
a[j-1]=a[j];
a[j]=y;
j=j-1;
}
/*
* TODO:
* - Change all mentions of io_buffer and IO_BUFFER_SIZE
* to input_buffer and INPUT_BUFFER_SIZE. The identifier
* is misleading as there is no output performed through
* the buffer.
*
* - Check the return values of fprintf and printf,
* something might go wrong in the output as well
* as the input, just checking the input is not
* enough.
*
* - Find a more scalable solution, the current solution
* is inefficient, but at least it is robust.
*
* - Add constants for the legal values of first input
* parameter n, currently they are hardcoded in the middle
* of file see lines 171-177.
*
* Maybe:
* - Migrate to stdbool.h, which provides a boolean type
* for details see ``stdbool.h''.
*/
#ifdef __bool_true_false_are_defined
/* this means that stdbool has been included
at a higher level */
/* we use the higher level bool type in
case the compiler optimizes some of
its use */
# define boolean bool
#else /* not __bool_true_false_are_defined */
/* we make our own boolean type */
/**
* @enum boolean
*
* @brief assumes one of two possible values true and false
*
* @true branches on an if-test represents truth, integrity and honesty
* @false does not branch on an if-test represents lies, falsehood and trickery
*/
typedef enum {
false = 0,
true = 1
} _boolean;
# define boolean _boolean
#endif /* __bool_true_false_are_defined */
/*
* CONSTANTS
*/
/**
* @constant LOWEST_VALUE
* @value 0
*
* @brief lowest possible value for input number
*/
#define LOWEST_VALUE 0
/**
* @constant HIGHEST_VALUE
* @value 65535
*
* @brief highest possible value for an input number
*/
#define HIGHEST_VALUE 65535
/**
* @constant NUMBER_RANGE
* @value (HIGHEST_VALUE - LOWEST_VALUE)
*
* @brief represents the range of possible input values
*
* Note that there might be a small bug in this implementation,
* we assume that every number between LOWEST_VALUE and HIGHEST_VALUE
* are valid input numbers, if this is not the case we might store
* an array of valid_numbers and things would look very different.
*/
#define NUMBER_RANGE (HIGHEST_VALUE-LOWEST_VALUE)
/**
* @constant IO_BUFFER_SIZE
* @value 256
*
* @brief size of input buffer in bytes
*/
#define IO_BUFFER_SIZE (256)
/* sanity checking is important. */
#if (HIGHEST_VALUE < LOWEST_VALUE)
# error "inane parameters for input number range"
#endif
/*
* GLOBALS
*/
/**
* @variable numbers
* @type boolean array
* @size NUMBER_RANGE + 1
*
* @brief holds true at the index of an input number and false otherwise
*
* The idea here is to store the input numbers based on their values.
* Will have all elements initialized to zero which is the same as
* @false.
*/
boolean numbers[NUMBER_RANGE + 1];
/*
* PROGRAM
*/
/**
* @function main
* @return (int) EXIT_SUCCESS on success or EXIT_FAILURE otherwise
*/
int main (void) {
/**
* @variable i
* @type int
* @default undefined
*
* @brief outer input for loop counter
*/
int i;
/**
* @variable n
* @type int
* @default 0
*
* @brief will hold the first input number
*
* Legal limits for this number is 5 <= n <= 100000.
*/
int n = 0;
/**
* @variable stored
* @type int
* @default 0
*
* @brief holds the number of inputted numbers
*/
int stored = 0;
if (fgets(io_buffer, IO_BUFFER_SIZE, stdin) == NULL) {
fprintf(stderr, "Error: no first parameter\n");
exit(EXIT_FAILURE);
} /* no input */
/* Read first parameter */
n = atoi(io_buffer);
if (n < 4 || n > 100000) {
fprintf(stderr,
"Error: invalid parameter %d\n"
"Must be in range 5 <= n <= 100000.\n",
n);
exit(EXIT_FAILURE);
} /* invalid input */
/* input loop */
for (i = 0; i < n; i++) {
/**
* @variable j
* @type int
* @default undefined
*
* @brief inner for-loop counter
*/
int j;
/**
* @variable endptr
* @type char *
* @default NULL
*
* @brief holds pointer to first invalid character in a string to integer conversion, see strtol (3) for details.
*/
char * endptr = NULL;
/**
* @variable first
* @type int
* @default undefined
*
* @brief holds the first input number from the stdin line ``number number''
*
* Legal limits for this number is 1 <= first <= 2.
*/
int first;
/**
* @variable second
* @type int
* @default undefined
*
* @brief holds the second input number from the stdin line ``number number''
*
* Legal limits for this number is based on @first.
* If @first is 1 then the limits are
* LOWEST_NUMBER <= second <= HIGHEST_NUMBER
* else if @first is 2 then the limits are
* 1 <= second <= stored
*/
int second;
/* we clear the input buffer
before reading a new line */
memset(io_buffer, '\0', IO_BUFFER_SIZE);
if (fgets(io_buffer, IO_BUFFER_SIZE, stdin) == NULL) {
fprintf(stderr,
"Error: expected input at line %d out of %d lines\n",
i, n);
exit(EXIT_FAILURE);
} /* no input */
/* a nonzero errno after
a strtol call means that
there was some error in
the string to integer
conversion phase */
/* for details on errno see
the POSIX entry on ``errno.h'' */
errno = 0;
first = strtol(io_buffer, &endptr, 0); /* read first number */
/* this is where the magic happens */
switch (first) {
case 1: /* first == 1 */
if (second < LOWEST_VALUE ||
second > HIGHEST_VALUE) {
fprintf(stderr,
"Error: invalid input size %d\n"
"Must be in range %d <= a <= %d.\n",
second,
LOWEST_VALUE, HIGHEST_VALUE);
exit(EXIT_FAILURE);
} /* invalid value */
/*
* We want to avoid artificially
* inflating stored in case we
* don't actually store a new number.
*
* The specifications stated clearly
* ``The total number of different number
* will not be bigger than 400, but some
* of the numbers can repeat!''.
*/
if (!numbers[second - LOWEST_VALUE])
stored += 1;
numbers[second - LOWEST_VALUE] = true;
break;
case 2: /* first == 2 */
if (second > stored) {
fprintf(stderr,
"Error: invalid input %d for second number\n"
"Tried to fetch the %d smallest input while only having stored %d numbers.\n",
second,
second, stored);
exit(EXIT_FAILURE);
} /* invalid value */
/* this is the inner loop where
we search for the smallest
number. */
for (j = 0; j < NUMBER_RANGE; j++)
if (numbers[j]) { /* found a number */
if (second == 1) { /* is it the one we're looking for? */
printf("%d\n", j + LOWEST_VALUE);
break;
} else { /* look again */
second -= 1;
}
} /* number found */
break;
default: /* illegal value for first */
fprintf(stderr,
"Error: invalid input %d for first number\n"
"Must be in {1, 2}.\n",
first);
exit(EXIT_FAILURE);
break;
}
}