sa

#include <bits/stdc++.h>


#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define LL long long
#define LOG(c) logger.log(c);


using namespace std;

const int64_t CYCLES_PER_SEC = 2500000000;
//const int64_t CYCLES_PER_SEC = 2800000000;
const double TIMELIMIT = 9.0;


class Logger {
public:
    ofstream outputfile;

    ~Logger(){
        outputfile.close();
    }

    void init(const string &fileName) {
        outputfile = ofstream(fileName, ios::app);
    }

    void log(const string &message) {
        outputfile << message << endl;
    }
};

class Timer {
    int64_t start;
public:
    Timer() {
        reset();
    }

    void reset() {
        this->start = getCycle();
    }

    inline double get() {
        return (double)(getCycle() - this->start) / CYCLES_PER_SEC;
    }

    inline int64_t getCycle() {
        uint32_t low, high;
        __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
        return ((int64_t)low) | ((int64_t)high << 32);
    }
};


class RandXor {
private:
    unsigned int x = 123456789;
    unsigned int y = 362436069;
    unsigned int z = 521288629;
    unsigned int w = 88675123;
public:
    RandXor() {
    }

    inline unsigned int random() {
        unsigned int t;
        t = (x ^ (x << 11)); x = y; y = z; z = w;
        return(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
    }

    // [0, a]
    unsigned int nextInt(int a) {
        return random() % a;
    }

    // [0, 1)
    double nextDouble() {
        return (random() + 0.5) * (1.0 / 4294967296.0);
    }

//    inline double rnd(){
//        return xor128() / 4294967296.0;
//    }
};

unsigned int N;             // 頂点数
vector<pair<int, int>> points;
Timer timer;
RandXor randxor;
Logger logger;


class State {
public:
    unsigned int N;
    vector<int> tour;
    double cost;

    explicit State(unsigned int n) : N(n) {
        tour = vector<int>(N);
        iota(ALL(tour), 0);
        evaluation();
    }

    explicit State(vector<int> tour) : N((unsigned int)tour.size()), tour(tour) {
        evaluation();
    }


    void evaluation() {
        this->cost = 0;
        for (int i = 0; i < tour.size(); ++i) {
            cost += att_distance(i, (i + 1) % N);
        }
    }

    void swap_position(int i, int j) {
        swap(this->tour.at(i), this->tour.at(j));
        cost += score_improvement_if_swapped(i, j);
    }

    double att_distance(int i, int j) {
        auto &p1 = points.at(tour.at(i));
        auto &p2 = points.at(tour.at((i + 1) % tour.size()));

        int dx = p1.first - p2.first;
        int dy = p1.second - p2.second;

        double r = sqrt((dy * dy + dx * dx) / 10);
        double t = round(r);
        return (t < r) ? t + 1 : t;
    }



    double score_improvement_if_swapped(int i, int j) {
        if (i > j) {
            swap(i, j);
        }
        if (i == j) {
            return 0;
        }
        if (i == 0 or i == 48 or j == 0 or j == 48) { return 0; }
        if (i + 1 == j) {
            double removedDist = att_distance(i - 1, i) + att_distance(i + 1, i + 2);
            double addedDist = att_distance(i - 1, i + 1) + att_distance(i, i + 2);
            double improvedDist = removedDist - addedDist;
            return improvedDist;
        } else {
            double removedDist = att_distance(i - 1, i) + att_distance(i, i + 1) +
                                 att_distance(j - 1, j) + att_distance(j, j + 1);
            double addedDist = att_distance(i - 1, j) + att_distance(j, i + 1) +
                               att_distance(j - 1, i) + att_distance(i, j + 1);
            double improvedDist = removedDist - addedDist;
            return improvedDist;
        }
    }

};


class SimulatedAnnealing {
private:
    // 温度関連
    const double start_temperature;
    const double end_temperature;
    double current_temperature;

    // 時間関連
    long long start_time;
    long long end_time;
    long long has_time; // 計算にかけることのできる時間

    // 冷却スケジュール
    const int shedule = -1;

    // その他
    int iter = 0;
    const int ITER_PER_SYNC = 16;  // 2^nである

public:
    enum CoolingSchedule {
        ExponentialMultiplicative,
        Time,
        Iter,
    };


    // start_temperature: 開始温度
    // end_temperature: 終了温度
    // remaining_time: 焼きなましに使える時間(sec)
    // schedule: CoolingScheduleから選ぶ
    SimulatedAnnealing(double start_temperature, double end_temperature, double remaining_time, CoolingSchedule schedule) : start_temperature(start_temperature),
                                                                                                                            current_temperature(start_temperature),
                                                                                                                            end_temperature(end_temperature),
                                                                                                                            shedule(schedule) {
        assert(schedule == ExponentialMultiplicative or schedule == Time or schedule == Iter);
        this->start_time = timer.getCycle();
        this->end_time = this->start_time + CYCLES_PER_SEC * remaining_time;
        this->has_time = this->end_time - this->start_time;
    }

    void cool_temperature() {
        if (start_temperature == 0) {
            return;
        }

        // 幾何冷却
        if (this->shedule == ExponentialMultiplicative) {
            if (this->current_temperature < this->end_temperature) {
                this->current_temperature = 0;
            } else {
                this->current_temperature *= 0.9;
            }

        }
            // 時間冷却
        else if (this->shedule == Time) {
            double done = (timer.getCycle() - this->start_time) / (1.0 * has_time);
            this->current_temperature = this->start_temperature * pow(end_temperature / start_temperature, done);
        }
            // 回数
        else if (this->shedule == Iter) {
            const int total = 10000;    // 全体でのiter回数
            this->current_temperature = this->start_temperature * pow(this->end_temperature / this->start_temperature, iter / total);
        }
        else {
            assert(false);
        }

    }

    // diffは負なら改善、正なら改悪
    bool do_transition(double diff) {
        this->iter++;

        // 温度の調整(ITER_PER_SYNC回ごとに1回やる)
        if (not (iter & (ITER_PER_SYNC - 1))) {
            this->cool_temperature();
        }

        bool accept;

        // 実質山登り法
        if (this->current_temperature == 0) {
            accept = diff < 0;
        }
        else {
            double probability = exp(-diff * this->current_temperature);
            accept = probability > randxor.nextDouble();
        }

        // log
//        cout << "iter:" + to_string(iter) + " current_temperature:" + to_string(current_temperature) +
//                " diff:" + to_string(diff) + " accept:" + to_string(accept) << endl;

        return accept;
    }

    string info() {
        return "SimulatedAnnealing(start temperature:" + to_string(this->start_temperature) +
               "end temperature:" + to_string(this->end_temperature) + ")";
    }

};

class Solution {
public:
    double best_cost;
    vector<int> best_tour;

    Solution() {}

    State run() {

//        vector<int> v = {1, 8, 38, 31, 44, 18, 7, 28, 6, 37, 19, 27, 17, 43, 30, 36, 46, 33, 20, 47, 21, 32, 39, 48, 5, 42, 24, 10, 45, 35, 4, 26, 2, 29, 34, 41, 16, 22, 3, 23, 14, 25, 13, 11, 12, 15, 40, 9};
//        vector<int> t;
//        for (int x: v) {
//            t.emplace_back(x - 1);
//        }

        State state = initial_solution();
        this->best_cost = state.cost;
        this->best_tour = state.tour;

        cout << "initial score:" + to_string(this->best_cost) << endl;

        // 焼きなまし
        double start_temperature = 1000;
        double end_temperature = 10;
        double remaining_time = 9.5;
        SimulatedAnnealing::CoolingSchedule schedule = SimulatedAnnealing::CoolingSchedule::Time;
        SimulatedAnnealing sa(start_temperature, end_temperature, remaining_time, schedule);
        LOG(sa.info());
        int iter = 0, num_of_improve = 0;
        for (;;++iter) {
            double now_time = timer.get();
            if (now_time > TIMELIMIT) {
                LOG("time up");
                break;
            }

            if (iter % 100000 == 0) {

            }

            bool improve = this->transition(state, sa);
            if (state.cost < this->best_cost) {
                cout << to_string(iter) + ":" + to_string(state.cost) << endl;
                this->best_cost = state.cost;
                this->best_tour = vector<int>(state.tour);
            }
            num_of_improve += improve;

        }
        cout << "" + to_string(num_of_improve) + "/" + to_string(iter) << endl;


        // SAでの最適解をコピー
        state.cost = this->best_cost;
        state.tour = this->best_tour;
        LOG("after score:" + to_string(state.cost));

        return state;
    }

    State initial_solution() {
        vector<int> tour(N);
        iota(tour.begin(), tour.end(), 0);
        random_shuffle(tour.begin(), tour.end());
        return State(tour);
    }

    bool transition(State &state, SimulatedAnnealing &sa) {

        int pos1 = randxor.nextInt(N);
        int pos2 = randxor.nextInt(N);

        // swapしたときのscoreのdiff
        double diff = state.score_improvement_if_swapped(pos1, pos2);

        bool do_change = sa.do_transition(diff);
        if (do_change) {
            state.swap_position(pos1, pos2);
            return true;
        }
        else {
            return false;
        }
    }
};


int main() {

    ifstream ifs("../att48.tsp");
    if (ifs.fail()) {
        cerr << "file not found" << endl;
        return -1;
    }
    string line;
    int no = 0;
    while (getline(ifs, line)){
        if (line == "EOF") {
            break;
        }
        if (5 < no) {
            istringstream iss(line);
            string a, b, c;
            iss >> a >> b >> c;
            points.emplace_back(make_pair(stoi(b), stoi(c)));
        }
        no++;
    }

    N = points.size();
    Solution solution;
    State state = solution.run();
    cout << "best:" << 10628 << endl;
    cout << "hill:" << 17050 << endl;
    cout << "sa:" << 16271 << endl;
    cout << "cost:" << state.cost <<  endl;
    cout << "tour:";
    for (int x : state.tour) {
        cout << x << " ";
    }
    cout << endl;


}