Recover the sequence

//
//  main.m
//  RecoverSequence
//
//  Created by Sidharth Juyal on 29/01/12.
//  Copyright (c) 2012 whackylabs. All rights reserved.
//

#import <Foundation/Foundation.h>
//#define D_BUG 1
#define PATH @"/Volumes/FreeAgent GoFlex Drive/Downloads/recover_the_sequence.txt"
typedef struct{
    int low, high;
}Marks;

static inline Marks MarksMake(int l, int h){
    Marks m;
    m.low = l;
    m.high = h;
    return m;
}

static inline int MarksDistance(Marks m){
    return m.high - m.low;
}

static inline NSString *MarksDesc(Marks m){
    return [NSString stringWithFormat:@"%d,%d",m.low,m.high];
}

@interface Solver: NSObject{
    int *indices_;
    int count_;
    int *debug_;
    int debug_count_;
}
-(Marks)mergeSortWithMarks:(Marks)m;
-(void) mergeArrayOne:(Marks )one two:(Marks )two;
-(int)checksum;
-(id)initWithCount:(int)n debugStr:(NSString *)dstr;
@end

@implementation Solver

-(Marks)mergeSortWithMarks:(Marks)m{
    int n = m.high - m.low + 1;
    if (n <= 1)
        return m;

    int mid = n/2;
    Marks first_half = [self mergeSortWithMarks:MarksMake(m.low, m.low+mid-1)];
    Marks second_half = [self mergeSortWithMarks:MarksMake(m.low+mid, m.high)];
    [self mergeArrayOne:first_half two:second_half];                        //merge(first_half, second_half);
    return m;
}

-(void) mergeArrayOne:(Marks )one two:(Marks )two{
    int arr1p = one.low;
    int arr2p = two.low;
    int *cache = (int *)malloc(sizeof(int) * (MarksDistance(one)+MarksDistance(two)));
    int cachep = 0;
    while (arr1p <= one.high && arr2p <= two.high){
        int d_val = debug_[debug_count_++];
        if(d_val == 0){
            cache[cachep++] = indices_[arr1p++];
        }else{
            cache[cachep++] = indices_[arr2p++];
        }
    }

    while (arr1p <= one.high) {
        cache[cachep++] = indices_[arr1p++];
    }
    while (arr2p <= two.high) {
        cache[cachep++] = indices_[arr2p++];
    }

    arr1p = one.low;
    arr2p = two.low;
    cachep = 0;
    while (arr1p <= one.high) {
        indices_[arr1p++] = cache[cachep++];
    }
    while (arr2p <= two.high) {
        indices_[arr2p++] = cache[cachep++];
    }
    free(cache);
}

-(int)checksum{
#ifdef D_BUG
    printf("Indices:\n");
#endif
    int result = 1;
    int i,j;
    int *arr = (int *)malloc(sizeof(int) * count_);
    for(int i = 0; i < count_; i++)
        arr[i] = i+1;
    for(i = 0; i < count_; i++){
        for(j = 0; j < count_; j++)
            if(i == indices_[j])
                break;
#ifdef D_BUG
        printf("arr[%d] = %d ",i,arr[j]);
#endif
        result = (31 * result + arr[j]) % 1000003;
    }
#ifdef D_BUG
    printf("\n");
#endif
    free(arr);
    return result;
}

-(id)initWithCount:(int)n debugStr:(NSString *)dstr{
    self = [super init];
    if(self){
        count_ = n;
        indices_ = (int *)malloc(sizeof(int) * count_);
        for(int i = 0; i < n; i++)
            indices_[i] = i;
        debug_ = (int *)malloc(sizeof(int)*[dstr length]);
        for(int i = 0; i < [dstr length]; i++)
            debug_[i] = [dstr characterAtIndex:i] == '1'?0:1;
        debug_count_ = 0;
        [self mergeSortWithMarks:MarksMake(0, count_-1)];
    }
    return self;
}

-(void)dealloc{
    free(indices_);
    free(debug_);
    [super dealloc];
}

@end

int main (int argc, const char * argv[]){
    @autoreleasepool {
        NSString *str = [[NSString alloc] initWithContentsOfFile:PATH encoding:NSUTF8StringEncoding error:nil];
        NSArray *words = [str componentsSeparatedByCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]];
        int w_no = 0;
        int cases = [[words objectAtIndex:w_no++] intValue];
        for(int c = 0; c < cases; c++){
            int n = [[words objectAtIndex:w_no++] intValue];
            Solver *s = [[Solver alloc] initWithCount:n debugStr:[words objectAtIndex:w_no++]];
            int checksum = [s checksum];
            [s release];
            printf("Case #%d: %d\n",c+1,checksum);
        }
        [str release];
    }
    return 0;
}