Facebook Hacker Cup 2012 - Recover the Sequence (Round 1)

gistfile1.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace hackercup2012_1
{
    class q2
    {
        static StreamReader ip = new StreamReader("input.txt");
        static StreamWriter op = new StreamWriter("output.txt");

        static List<int> merge_sort(List<int> arr)
        {
            var n = arr.Count;
            if (n <= 1)
                return arr;

            // arr is indexed 0 through n-1, inclusive
            var mid = n / 2;
    
            var first_half = merge_sort(arr.Take(mid).ToList());
            var second_half = merge_sort(arr.Skip(mid).ToList());
            return merge(first_half, second_half);
        }

        static List<int> merge(List<int> arr1, List<int> arr2)
        {
            var result = new List<int>();
            while (arr1.Count > 0 && arr2.Count > 0)
            {
                var bt = ip.Read();
                if (bt == '1')
                {
                    result.Add(arr1[0]);
                    arr1.RemoveAt(0);
                }
                else
                {
                    result.Add(arr2[0]);
                    arr2.RemoveAt(0);
                }
            }
            result.AddRange(arr1);
            result.AddRange(arr2);
            return result;
        }

        static ulong checksum(List<int> arr)
        {
            return arr.Aggregate(1ul, (x, y) => (31ul * x + (ulong)y) % 1000003ul);
        }

        static void Main(string[] args)
        {
            int t = int.Parse(ip.ReadLine());
            for (int i = 0; i < t; i++)
            {
                var N = int.Parse(ip.ReadLine());
                var da = new List<int>();
                for (int j = 0; j < N; j++)
                    da.Add(j);
                da = merge_sort(da);
                var db = new int[N];
                for (int j = 0; j < N; j++)
                    db[da[j]] = j + 1;
                op.WriteLine("Case " + (i + 1) + ": " + checksum(db.ToList()));
                ip.ReadLine();
            }

            ip.Close();
            op.Close();
        }
    }
}