MM26 C++ Solution (check time every times)

Permute.cpp

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

#ifdef _MSC_VER
#   include <chrono>
    inline auto get_time() {
	   return std::chrono::system_clock::now();
    }
    inline auto to_msec(int t) {
	   return std::chrono::milliseconds(t);
    }
    typedef std::chrono::system_clock::time_point Time;
#else
    const double ticks_per_sec = 2800000000;
    inline double get_time() {
	   uint32_t lo, hi;
	   asm volatile ("rdtsc" : "=a" (lo), "=d" (hi));
	   return (((uint64_t)hi << 32) | lo) / ticks_per_sec;
    }
    inline double to_msec(int t) {
	   return double(t) / 1000.0;
    }
    typedef double Time;
#endif

using namespace std;

class Permute {
public:
    int limit;
    Permute() : limit(29800) {}
    vector<int> findOrder(vector<double> w) {
        auto time0  = get_time() + to_msec(limit);
        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;
        
        for (;;) {
        
            auto time1 = get_time();
            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 * sqrt((double)n * log((double)n) - (double)n) / 100.0;
        sc /= dv;
        
        cerr << "score=" << sc << endl;
        cerr << "loop=" << lp << endl;
        
        return ret;
    }
};