MM26 C++ Solution (5800000 cycles)

Permute.cpp

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

class Permute {
public:
    long long limit;
    Permute() : limit(5800000) {}
    vector<int> findOrder(vector<double> w) {
        const int n = (int)sqrt((double)w.size());
        vector<int> ret(n);
        for (int i = 0; i < n; i++) {
            ret[i] = i;
        }
        
        double sc = 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 long lp = 0;
        int a = 0, b = 1;
        
        while (lp < limit) {
        
            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 * sqrt((double)n * log((double)n) - (double)n) / 100.0;
        sc /= dv;
        
        cerr << "score=" << sc << endl;
        cerr << "loop=" << lp << endl;
        
        return ret;
    }
};