Listen to your compiler
Before any refactoring, you should address the compiler warnings:
gcc-7 -std=c11 -fPIC -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wconversion 175458.c -o 175458
175458.c: In function ‘gcd’:
175458.c:7:23: warning: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Wsign-conversion]
shift = __builtin_ctz(u | v);
^
175458.c:8:21: warning: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Wsign-conversion]
u >>= __builtin_ctz(u);
^
175458.c:10:25: warning: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Wsign-conversion]
v >>= __builtin_ctz(v);
^
175458.c:12:24: warning: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Wsign-conversion]
unsigned int t=v;
^
175458.c:14:11: warning: conversion to ‘int’ from ‘unsigned int’ may change the sign of the result [-Wsign-conversion]
u=t;
^
175458.c: In function ‘main’:
175458.c:102:23: warning: implicit declaration of function ‘malloc’ [-Wimplicit-function-declaration]
char *arr=(char *)malloc(arr_size * sizeof(char));
^~~~~~
175458.c:102:23: warning: incompatible implicit declaration of built-in function ‘malloc’
175458.c:102:23: note: include ‘<stdlib.h>’ or provide a declaration of ‘malloc’
175458.c:102:39: warning: conversion to ‘long unsigned int’ from ‘int’ may change the sign of the result [-Wsign-conversion]
char *arr=(char *)malloc(arr_size * sizeof(char));
^
175458.c:128:5: warning: implicit declaration of function ‘free’ [-Wimplicit-function-declaration]
free(arr);
^~~~
175458.c:128:5: warning: incompatible implicit declaration of built-in function ‘free’
175458.c:128:5: note: include ‘<stdlib.h>’ or provide a declaration of ‘free’
Use whitespace and meaningful names
Dense code with single-letter variable names is hard to read. Use meaningful names; the few exceptions can be where a variable has sufficiently small scope (within ten lines or so).
Use whitespace to separate logical parts of the program. Typically, use a blank line or two between functions, and a blank line between sections within a function. Space around operators and names can also be helpful.
Choose your types carefully
The problem says that inputs may be as large as a million. Standard int is guaranteed to be able to represent the range -32768 to +32767, which is not enough. Instead of assuming that int is 21 bits or more, it's worth verifying (and we don't allow negative values, so let's use unsigned types):
#include <limits.h>
#if UINT_MAX < 1000000
typedef unsigned long Integer;
#define SCN_FMT "%lu"
#define PRI_FMT "%lu"
#else
typedef unsigned int Integer;
#define SCN_FMT "%u"
#define PRI_FMT "%u"
#endif
Alternatively, we could always use long unsigned int, which must be able to represent our maximum value.
If we include <stdint.h>, then we can use uint_fast32_t, which may be our best choice:
#include <stdint.h>
#include <inttypes.h>
typedef uint_fast32_t Integer;
#define SCN_FMT "%" SCNuFAST32
#define PRI_FMT "%" PRIuFAST32
Use a simpler GCD implementation
Reducing a fraction to its lowest terms is much more simply expressed as
Integer gcd(Integer a, Integer b)
{
/* Recursive implementation of Euclid's algorithm */
return b ? a : gcd(b, a % b);
}
Although a well-implemented binary GCD may be 20% faster than the Euclidean method, this isn't the performance-critical part of the code (and a good compiler will optimise it well, including transformation of the recursive tail-call to iterative form), so why not just write it clearly?
Split the long query method
Instead of one huge function, we can factor out the counting and the printing, and we can avoid duplicating the even and odd counting (when we know how many even elements we have, and the total count, then there are total-even odd elements).
void print_reduced_fraction(Integer numerator, Integer denominator)
{
if (numerator == 0) {
printf("0\n");
} else if (numerator == denominator) {
printf("1\n");
} else {
Integer divisor = 1;gcd(numerator, denominator);
printf(PRI_FMT " " PRI_FMT "\n",
numerator/divisor, denominator/divisor);
}
}
Integer count_odd(const unsigned char *p, const unsigned char *end)
{
Integer n = 0;
/* N.B. end is INCLUSIVE */
while (p <= end)
n += *p++;
return n;
}
void query(const unsigned char *arr, int qtype, Integer l, Integer r, char v)
{
if (qtype == 2 && v) {
for (unsigned char *p = arr+l; p <= arr+r; ++p)
*p ^= 1;
return;
}
Integer total = r + 1 - l;
Integer odd = count_odd(arr+l, arr+r);
Integer even = total - odd;
print_reduced_fraction(qtype ? odd : even, total);
}
Now the qtype == 2 test is really switching between completely different code paths - well worth separating into two functions.
Check return values from library calls
scanf() and malloc() can both fail - we can't reasonably continue if they do. printf() could fail, but we might choose to ignore that and continue regardless.
int die(const char *message)
{
fprintf(stderr, message);
return EXIT_FAILURE;
}
int main()
{
size_t tests_remaining;
if (scanf("%zu", &tests_remaining) != 1)
return die("Failed to read testcase count!\n");
while (tests_remaining--) {
size_t array_size;
int queries_remaining;
if (scanf("%zu%d", &array_size, &queries_remaining) != 2)
return die("Failed to read array size and query count!\n");
unsigned char *array = malloc(array_size * sizeof *array);
if (!array)
return die("Failed to allocate memory");
for(size_t i = 0; i < array_size; ++i) {
int x;
if (scanf("%d", &x) != 1)
return die("Failed to read array value");
array[i] = x & 1;
}
while(queries_remaining--) {
int query_type;
Integer left, right;
if (scanf("%i" SCN_FMT SCN_FMT, &query_type, &left, &right) != 3)
return die("Failed to read ");
/* left and right are 1-based, so subtract to index the array correctly */
unsigned char *first = array + --left;
unsigned char *last = array + --right;
switch (query_type) {
case 0:
case 1:
{
Integer total = right + 1 - left;
Integer odd = count_odd(first, last);
Integer even = total - odd;
print_reduced_fraction(query_type ? odd : even, total);
}
break;
case 2:
{
int addend;
if (scanf("%d",&addend) != 1)
return die("Failed to read update value\n");
if (addend & 1) {
/* invert values in range, inclusive */
while (first <= last)
*first++ ^= 1;
}
}
break;
default:
return die("Invalid query type\n");
}
}
free(array);
}
}
Consider an alternative representation
Instead of accessing every element in the range of a count, it may be faster to store an array of Integer (or perhaps uint_least32_t) containing the running sum of odd elements. Then the search operations require just two accesses and a single subtraction.
This representation does likely increase the storage cost of the implementation (with concomitant effects on cache misses, etc). That's likely to have an impact on update operations (query type 2), but is probably worth trying.
It could have a big impact on updates; one mitigation would be to keep note of updates (only those with odd summand, obviously) in a separate structure (of non-overlapping ranges), and use them to apply corrections to the raw counts from the unmodified input array.
The good news is that having refactored into individual methods, most of them are unaffected by the change in representation, so it was well worth doing that first!
#pragma omp. But that obviously doesn't help throughput if you're already running many instances simultaneously. And the performance of the memory hierarchy will have a great effect on timings, too. \$\endgroup\$ – Toby Speight Oct 17 '17 at 15:19