MM26 C# Solution (optimal call check time)

Permute.cs

using System;

public class Permute
{
    public int limit = 29800;
    public int[] findOrder(double[] w)
    {
        int time0 = Environment.TickCount + limit;
        
        int n = (int)Math.Sqrt((double)w.Length);
        var ret = new int[n];
        for (int i = 0; i < n; i++)
        {
            ret[i] = i;
        }
        
        double sc = 0.0;
        for (int i = 0; i < n - 1; i++)
        {
            int rn = ret[i] * n;
            for (int j = i + 1; j < n; j++)
            {
                sc += w[rn + ret[j]];
            }
        }
        
        long lp = 0;
        int a = 0, b = 1;
        
        for (;;)
        {
            if ((lp & 8191) == 0)
            {
                int time1 = Environment.TickCount;
                if (time1 > time0)
                {
                    break;
                }
            }
            
            lp++;
            
            int ra = ret[a];
            int rb = ret[b];
            int ran = ra * n;
            int rbn = rb * n;
            
            double dsc = w[rbn + ra] - w[ran + rb];
            for (int i = a + 1; i < b; i++)
            {
                int r = ret[i];
                int rn = r * n;
                dsc += w[rbn + r] + w[rn + ra] - w[ran + r] - w[rn + rb];
            }
            
            if (dsc > 0.0)
            {
                ret[a] = rb;
                ret[b] = ra;
                sc += dsc;
            }
            
            b++;
            if (b >= n)
            {
                a++;
                if (a >= n - 1)
                {
                    a = 0;
                }
                b = a + 1;
            }
        }
        
        double dv = (double)n * Math.Sqrt((double)n * Math.Log((double)n) - (double)n) / 100.0;
        sc /= dv;
        
        Console.Error.WriteLine("score={0}", sc);
        Console.Error.WriteLine("loop={0}", lp);
        
        return ret;
    }
}