Efficient coding ensures that you complete a task in the smallest time interval possible without complicating your life too much. Now, you do not need to work like this for every little bit of code you type. This approach will be priceless, however, whenever time is of the essence, as it is for a programming contest.
Easy and Efficient Programming for Contests - Macros, arrays and memory (Page 3 of 4 )
Avoid using macros for functions. You can lose points for a simple construction as follows:
#define MAX (a, b) ((a) < (b)? (b) : (a))
int query(int a, int b)
int k, l, r;
int result = 0;
result = MAX(k, query(l, r));
Observe that sometimes, the MAX is called twice; it's best to avoid this situation during a contest. Instead, use a function declared as inline:
inline int MAX(int a, int b)
if(a > b)
Most of the time at a contest, the input and output of the program is a file. From this, you can already conclude that you need to use a lot of fscanf and fprintf. However, there is a solution for this. You can bind both of the files to the standard input and output with the function freopen (for newer compilers this has been declared deprecated and there exists a secure version of it).
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
This is easy, and from now on, you can read and print all of your files using the scanf and prinft functions, making your life easier and your code a little simpler. Every now and then, you may want to use arrays with negative indexing.
Everyone who is familiar with the Pascal language knows that this was possible with it. Nevertheless, creating arrays in this way is not an option in C/C++, however we can trick the system using the following macro definition.
#define A (A + 100)
Now you have an array that you can index from -100 to 100. In addition, it is advisable to use the ++i operator instead of i++; executing the first will be faster. As for the second, a local variable will be created to calculate the new value for i. Creating variables this small (int) is not a big task, but it is still an additional task. The situation changes when you use STL and use the operator for iterators. In that case, do not ever use the second construction, as that will lead to a slow execution of your program.
For infinite values, I recommend that you use either one of the following:
#define INFINITY 0X3F
#define INFINITY INT_MAX/2
This will be most of the time large enough for the input files and INFINITY plus INFINITY will remain positive and fit inside the int. For setting default values for an array use the memset function.
// allocate place using malloc for array_2
memset( array_1, 0XFF, sizeof(array_1)); // -1 at every place