Submission #1051195

---

Source Code Expand

#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
#define U(v) \
cerr << #v << ": " << (v) << endl

class timer {
    int n = 0;
    map<string, timer> ts;
public:
    long long limit = 9700;
    long long t = 0;
    bool elapses() const {
        return time() - t > limit;
    }
    void measure() {
        t = time() - t;
        ++n;
    }
    void measure(const string& id) {
        ts[id].measure();
    }
    void print(const string& id = "TOTAL") {
        if (n % 2 && id == "TOTAL")
            measure();
        for (auto& p : ts)
            p.second.print(p.first);
        fprintf(stderr, "%9s: %4lld, %d\n", id.c_str(), t, n / 2);
    }
    static long long time() {
        return clock() * 1000ll / CLOCKS_PER_SEC;
    }
} timer;

class rando {
    unsigned y = 2463534242;
public:
    unsigned next() {
        return y ^= (y ^= (y ^= y << 13) >> 17) << 5;
    }
    int next(int b) {
        return next() % b;
    }
    int next(int a, int b) {
        return next(b - a) + a;
    }
    double next_double(double b = 1) {
        return b * next() / 4294967296.0;
    }
    double next_double(double a, double b) {
        return next_double(b - a) + a;
    }
    int operator() (int b) {
        return next(b);
    }
} rando;

template <typename Score>
class Annealing {
    const long long START_TIME;
    const double FINAL_HEAT, INITIAL_HEAT, HEAT_COEF;
    Score th;
    double heat;
public:
    Annealing(double initialHeat, double finalHeat, int timeLimit) :
        START_TIME(timer.time()),
        FINAL_HEAT(1 / finalHeat),
        INITIAL_HEAT(1 / initialHeat),
        HEAT_COEF(log(FINAL_HEAT / INITIAL_HEAT) / (timeLimit - START_TIME + timer.t)) {}
    bool cool() {
        heat = INITIAL_HEAT * exp((timer.time() - START_TIME) * HEAT_COEF);
        th = (Score)(7 / heat);
        return heat < FINAL_HEAT;
    }
    bool should_transit(Score diff) const {
        return diff < 1 || diff < th && rando.next_double() < exp(-diff * heat);
    }
};

struct Node {
    int x, y, height, forward = 0, reverse = 0;
    Node* begin, * end, * prev = nullptr, * next = nullptr;
    Node() {}
    Node(int x, int y, int height) : x(x), y(y), height(height) {}
};

const int N = 30;
const int KEEP = 2048;
Node best_sols[KEEP][N][N];
int best_scores[KEEP];

namespace Annealer {

    int diff(Node* n1, Node* n2) {
        return max(0, n1->height - n2->height + 1);
    }

    int evalf(Node* n) {
        return n->end->forward + n->end->height;
    }

    int evalr(Node* n) {
        return n->begin->reverse + n->begin->height;
    }

    int eval(Node* n) {
        return min(evalf(n), evalr(n));
    }

    int eval(Node* n1, Node* n2) {
        return (n1->next ? n1->reverse : n1->forward) +
            diff(n1, n2) + (n2->next ? evalf(n2) : evalr(n2));
    }

    int evalf(Node* n1, Node* n2) {
        return n2->forward + n2->height - n1->forward;
    }

    int evalr(Node* n1, Node* n2) {
        return n2->reverse + n2->height - n1->reverse;
    }

    int evalff(Node* n1, Node* n2) {
        return min(n1->forward + diff(n1, n2) + evalf(n2, n2->end),
            n2->reverse + diff(n2, n1) + evalr(n1, n1->begin));
    }

    int evalfr(Node* n1, Node* n2) {
        return min(n1->forward + diff(n1, n2) + evalr(n2, n2->begin),
            n2->forward + diff(n2, n1) + evalr(n1, n1->begin));
    }

    int evalrf(Node* n1, Node* n2) {
        return min(n1->reverse + diff(n1, n2) + evalf(n2, n2->end),
            n2->reverse + diff(n2, n1) + evalf(n1, n1->end));
    }

    int eval1(Node* n1, Node* n2) {
        return min(evalf(n1, n2), evalr(n2, n1));
    }

    int eval(Node sol[][N]) {
        int score = 0;
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < N; ++x) {
                auto n = &sol[y][x];
                if (n == n->begin)
                    score += eval(n);
            }
        }
        return score;
    }

    int manhattan(Node* n1, Node* n2) {
        return abs(n1->x - n2->x) + abs(n1->y - n2->y);
    }

    vector<Node> cells(Node* n) { 
        vector<Node> cells;
        if (evalf(n) < evalr(n)) {
            for (; n; n = n->next)
                cells.push_back(*n);
        } else {
            for (n = n->end; n; n = n->prev)
                cells.push_back(*n);
        }
        return cells;
    }

    void update(Node* b, Node* e) {
        b->begin = b;
        b->end = e;
        b->prev = nullptr;
        e->next = nullptr;
        b->forward = 0;
        for (auto n = b->next; n; n = n->next) {
            n->begin = b;
            n->end = e;
            n->forward = n->prev->forward + diff(n->prev, n);
        }
        e->reverse = 0;
        for (auto n = e->prev; n; n = n->prev)
            n->reverse = n->next->reverse + diff(n->next, n);
    }

    void updateff(Node* b1, Node* b2, Node* e1, Node* e2) {
        b2->next = e1;
        e1->prev = b2;
        update(b1, e2);
    }

    void updatefr(Node* b1, Node* b2, Node* e1, Node* e2) {
        e2->prev = nullptr;
        for (auto n = e1; n; n = n->next)
            swap(n->next, n->prev);
        updateff(b1, b2, e1, e2);
    }

    void updaterf(Node* b1, Node* b2, Node* e1, Node* e2) {
        b2->prev = nullptr;
        for (auto n = b1; n; n = n->next)
            swap(n->next, n->prev);
        updateff(b1, b2, e1, e2);
    }

    void copy(Node from[][N], Node to[][N]) {
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < N; ++x) {
                auto& f = from[y][x];
                auto& t = to[y][x];
                t.forward = f.forward;
                t.reverse = f.reverse;
                t.begin = &to[f.begin->y][f.begin->x];
                t.end = &to[f.end->y][f.end->x];
                t.prev = f.prev ? &to[f.prev->y][f.prev->x] : nullptr;
                t.next = f.next ? &to[f.next->y][f.next->x] : nullptr;
            }
        }
    }

    Node sol[N][N];
    int score;
    int best_i;

    void transit(int diff) {
        score += diff;
        if (best_scores[best_i] > score) {
            best_scores[best_i] = score;
            copy(sol, best_sols[best_i]);
        }
    }

    void anneal() {
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < N; ++x) {
                int height;
                cin >> height;
                sol[y][x] = { x, y, height };
                sol[y][x].begin = sol[y][x].end = &sol[y][x];
                for (auto& s : best_sols)
                    s[y][x] = Node(x, y, height);
            }
        }
        score = eval(sol);
        fill_n(best_scores, KEEP, score);
        best_i = -1;
        Annealing<int> sa(
            45000,
            0.7,
            7500
        );
        for (int an = -1; ; ) {
            if (!(++an & 0x7ff)) {
                if (!sa.cool()) break;
                best_i = (best_i + 1) % KEEP;
            }

            // select randomly adjacent two cells
            unsigned r = rando.next();
            Node* n1;
            Node* n2;
            {
                int x = (r & 0x7fff) % (N - 1);
                int y = (r >> 17) % N;
                if (r & 0x8000) {
                    n1 = &sol[y][x];
                    n2 = &sol[y][x + 1];
                } else {
                    n1 = &sol[x][y];
                    n2 = &sol[x + 1][y];
                }
            }

            // neighbor1 split one path to two paths
            if (n1->prev == n2 || n1->next == n2) {
                if (n1->prev == n2)
                    swap(n1, n2);
                int curr_score = eval(n1);
                int cand_score = eval1(n1->begin, n1) + eval1(n2, n2->end);
                int diff = cand_score - curr_score;
                if (sa.should_transit(diff)) {
                    update(n1->begin, n1);
                    update(n2, n2->end);
                    transit(diff);
                }

            } else if ((n1->prev && n1->next) != (n2->prev && n2->next)) {
                if (n1->prev && n1->next)
                    swap(n1, n2);

                // neighbor3 split one path includes n2 to two paths. combine splitted one path and one path includes n1
                if (n1->begin != n2->begin) {
                    int curr_score = eval(n1) + eval(n2);
                    int s1 = (n1->next ? n1->reverse : n1->forward) + diff(n1, n2);
                    int s2 = diff(n2, n1) + (n1->next ? evalf(n1) : evalr(n1));
                    if (r & 0x10000) {
                        int cand_score = min(s1 + evalr(n2, n2->begin), n2->forward + s2) + eval1(n2->next, n2->end);
                        int diff = cand_score - curr_score;
                        if (sa.should_transit(diff)) {
                            update(n2->next, n2->end);
                            if (n1->next)
                                updateff(n2->begin, n2, n1, n1->end);
                            else
                                updatefr(n2->begin, n2, n1, n1->begin);
                            transit(diff);
                        }
                    } else {
                        int cand_score = min(s1 + evalf(n2, n2->end), n2->reverse + s2) + eval1(n2->begin, n2->prev);
                        int diff = cand_score - curr_score;
                        if (sa.should_transit(diff)) {
                            update(n2->begin, n2->prev);
                            if (n1->next)
                                updaterf(n1->end, n1, n2, n2->end);
                            else
                                updateff(n1->begin, n1, n2, n2->end);
                            transit(diff);
                        }
                    }

                    // neighbor4 split and combine one path
                } else {
                    int curr_score = eval(n1);
                    if (n1->next) {
                        int cand_score = min(n2->reverse + diff(n2, n1) + evalf(n1, n2->prev),
                            n1->reverse - n2->prev->reverse + diff(n1, n2) + evalf(n2, n2->end));
                        int diff = cand_score - curr_score;
                        if (sa.should_transit(diff)) {
                            updaterf(n2->end, n2, n1, n2->prev);
                            transit(diff);
                        }
                    } else {
                        int cand_score = min(n2->forward + diff(n2, n1) + evalr(n1, n2->next),
                            n1->forward - n2->next->forward + diff(n1, n2) + evalr(n2, n2->begin));
                        int diff = cand_score - curr_score;
                        if (sa.should_transit(diff)) {
                            updatefr(n2->begin, n2, n1, n2->next);
                            transit(diff);
                        }
                    }
                }

                // neighbor5 combine two paths to one path
            } else if (!n1->prev || !n1->next) {
                if (n1->begin == n2->begin) continue;
                int curr_score = eval(n1) + eval(n2);
                int cand_score = min(eval(n1, n2), eval(n2, n1));
                int diff = cand_score - curr_score;
                if (sa.should_transit(diff)) {
                    if (n1->next && n2->next) {
                        updaterf(n1->end, n1, n2, n2->end);
                    } else if (n1->next) {
                        updateff(n2->begin, n2, n1, n1->end);
                    } else if (n2->next) {
                        updateff(n1->begin, n1, n2, n2->end);
                    } else {
                        updatefr(n1->begin, n1, n2, n2->begin);
                    }
                    transit(diff);
                }

                // neighbor2 split and combine two paths
            } else {
                if (n1->begin == n2->begin) continue;
                int curr_score = eval(n1) + eval(n2);
                if (manhattan(n1->prev, n2->prev) == 1) {
                    int cand_score = evalfr(n1->prev, n2->prev) + evalrf(n1, n2);
                    int diff = cand_score - curr_score;
                    if (sa.should_transit(diff)) {
                        updatefr(n1->begin, n1->prev, n2->prev, n2->begin);
                        updaterf(n1->end, n1, n2, n2->end);
                        transit(diff);
                    }
                } else if (manhattan(n1->prev, n2->next) == 1) {
                    int cand_score = evalff(n1->prev, n2->next) + evalff(n2, n1);
                    int diff = cand_score - curr_score;
                    if (sa.should_transit(diff)) {
                        updateff(n1->begin, n1->prev, n2->next, n2->end);
                        updateff(n2->begin, n2, n1, n1->end);
                        transit(diff);
                    }
                } else if (manhattan(n1->next, n2->prev) == 1) {
                    int cand_score = evalff(n2->prev, n1->next) + evalff(n1, n2);
                    int diff = cand_score - curr_score;
                    if (sa.should_transit(diff)) {
                        updateff(n2->begin, n2->prev, n1->next, n1->end);
                        updateff(n1->begin, n1, n2, n2->end);
                        transit(diff);
                    }
                } else if (manhattan(n1->next, n2->next) == 1) {
                    int cand_score = evalrf(n1->next, n2->next) + evalfr(n1, n2);
                    int diff = cand_score - curr_score;
                    if (sa.should_transit(diff)) {
                        updaterf(n1->end, n1->next, n2->next, n2->end);
                        updatefr(n1->begin, n1, n2, n2->begin);
                        transit(diff);
                    }
                }
            }
        }
    }
}

namespace StepConnector {

    using Edge = array<pair<int, int>, 2>;

    vector<vector<Edge>> edges;
    int another_x;
    int another_y;
    int dp[128][128][2];

    int dfs(int x, int y, bool reverse) {
        int& ret = dp[y][x][reverse];
        if (ret >= 0)
            return ret;
        auto& e = edges[y][x][reverse];
        if (e.first >= 0 && (e.first == edges[y][x][!reverse].first || !dfs(e.second, e.first, reverse)))
            return ret = 0;
        int end = y == another_y && x > another_x ? another_x : -1;
        while (--x > end) {
            auto& e = edges[y][x];
            if (e[0].first >= 0 && !dfs(e[0].second, e[0].first, false))
                return ret = 0;
            if (e[1].first >= 0 && !dfs(e[1].second, e[1].first, true))
                return ret = 0;
        }
        return ret = y != another_y || x != another_x;
    }

    bool try_connect(const Edge& c) {
        auto& from = edges[c[0].first][c[0].second][0];
        auto& to = edges[c[1].first][c[1].second][1];
        if (from.first >= 0 || to.first >= 0)
            return false;
        from = c[1];
        to = c[0];
        for (int i = 0; i < 2; ++i) {
            another_x = c[1 - i].second;
            another_y = c[1 - i].first;
            for (int j = 0; j < (int)edges.size(); ++j)
                for (int k = 0; k < (int)edges[j].size(); ++k)
                    dp[j][k][0] = dp[j][k][1] = -1;
            fill_n(dp[another_y][another_x], 2, 0);
            if (!dfs(c[i].second, c[i].first, !i)) {
                from.first = -1;
                to.first = -1;
                return false;
            }
        }
        return true;
    }

    vector<Edge> connect(Node sol[][N], int n, int th) {
        static pair<int, int> step_begin[N][N][100];
        static pair<int, int> step_end[N][N][100];
        memset(step_begin, -1, sizeof step_begin);
        memset(step_end, -1, sizeof step_end);
        int paths_size = 0;
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < N; ++x) {
                auto n = &sol[y][x];
                if (n != n->begin) continue;
                auto cells = Annealer::cells(n);
                int path_size = 0;
                for (int i = 1; ; ) {
                    for (; i < (int)cells.size() && cells[i - 1].height < cells[i].height; ++i);
                    for (int j = i - 1; cells[i - 1].height >= (i == cells.size() ? 1 : cells[i].height); ) {
                        if (cells[j].height) {
                            for (; j && cells[j - 1].height && cells[j].height - cells[j - 1].height == 1; --j);
                        } else {
                            ++j;
                        }
                        for (int k = j; k < i; ++k)
                            --cells[k].height;
                        auto& b = cells[i - 1];
                        auto& e = cells[j];
                        step_begin[b.y][b.x][b.height] = { paths_size, path_size };
                        step_end[e.y][e.x][e.height] = { paths_size, path_size };
                        ++path_size;
                    }
                    if (i == cells.size()) break;
                }
                ++paths_size;
            }
        }
        vector<Edge> cands;
        vector<vector<int>> reindex(paths_size);
        for (int y = 0; y < N; ++y) {
            for (int x = 1; x < N; ++x) {
                for (int height = 1; height < 100; ++height) {
                    {
                        auto& p = step_end[y][x][height];
                        auto& q = step_begin[y][x - 1][height - 1];
                        if (p.first != -1 && q.first != -1 && p.first != q.first) {
                            cands.emplace_back(Edge{ p, q });
                            reindex[p.first].emplace_back(p.second);
                            reindex[q.first].emplace_back(q.second);
                        }
                    } {
                        auto& p = step_end[y][x - 1][height];
                        auto& q = step_begin[y][x][height - 1];
                        if (p.first != -1 && q.first != -1 && p.first != q.first) {
                            cands.emplace_back(Edge{ p, q });
                            reindex[p.first].emplace_back(p.second);
                            reindex[q.first].emplace_back(q.second);
                        }
                    } {
                        auto& p = step_end[x][y][height];
                        auto& q = step_begin[x - 1][y][height - 1];
                        if (p.first != -1 && q.first != -1 && p.first != q.first) {
                            cands.emplace_back(Edge{ p, q });
                            reindex[p.first].emplace_back(p.second);
                            reindex[q.first].emplace_back(q.second);
                        }
                    } {
                        auto& p = step_end[x - 1][y][height];
                        auto& q = step_begin[x][y][height - 1];
                        if (p.first != -1 && q.first != -1 && p.first != q.first) {
                            cands.emplace_back(Edge{ p, q });
                            reindex[p.first].emplace_back(p.second);
                            reindex[q.first].emplace_back(q.second);
                        }
                    }
                }
            }
        }
        if ((int)cands.size() <= th)
            return {};
        for (auto& a : reindex) {
            sort(a.begin(), a.end());
            a.erase(unique(a.begin(), a.end()), a.end());
        }
        for (auto& c : cands) {
            for (auto& p : c) {
                auto& a = reindex[p.first];
                p.second = find(a.begin(), a.end(), p.second) - a.begin();
            }
        }
        edges.resize(paths_size);
        for (int i = 0; i < paths_size; ++i)
            edges[i].assign(reindex[i].size(), {});
        vector<Edge> best_sol;
        for (int i = 0; i < n; ++i) {
            for (auto& es : edges)
                for (auto& e : es)
                    e[0].first = e[1].first = -1;
            random_shuffle(cands.begin(), cands.end(), rando);
            vector<Edge> sol;
            for (auto& c : cands) {
                if (try_connect(c))
                    sol.push_back(c);
            }
            if (best_sol.size() < sol.size())
                best_sol = sol;
        }
        for (auto& e : best_sol)
            for (auto& p : e)
                p.second = reindex[p.first][p.second];
        return best_sol;
    }

    void print(Node sol1[][N], const vector<Edge>& sol2) {
        vector<vector<vector<int>>> paths;
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < N; ++x) {
                auto n = &sol1[y][x];
                if (n != n->begin) continue;
                auto cells = Annealer::cells(n);
                vector<vector<int>> path;
                for (int i = 1; ; ) {
                    for (; i < (int)cells.size() && cells[i - 1].height < cells[i].height; ++i);
                    for (int j = i - 1; cells[i - 1].height >= (i == cells.size() ? 1 : cells[i].height); ) {
                        if (cells[j].height) {
                            for (; j && cells[j - 1].height && cells[j].height - cells[j - 1].height == 1; --j);
                        } else {
                            ++j;
                        }
                        vector<int> step;
                        for (int k = i - 1; k >= j; --k) {
                            auto& c = cells[k];
                            --c.height;
                            step.emplace_back(c.x);
                            step.emplace_back(c.y);
                        }
                        path.emplace_back(step);
                    }
                    if (i == cells.size()) break;
                }
                paths.emplace_back(path);
            }
        }
        edges.resize(paths.size());
        for (int i = 0; i < (int)edges.size(); ++i)
            edges[i].assign(paths[i].size(), { make_pair(-1, 0), make_pair(-1, 0) });
        for (auto& e : sol2)
            for (int i = 0; i < 2; ++i)
                edges[e[i].first][e[i].second][i] = e[1 - i];
        vector<int> xs(paths.size(), 0);
        while (true) {
            bool any = false;
            for (int y = 0; y < (int)paths.size(); ++y) {
                while (xs[y] < (int)paths[y].size()) {
                    vector<pair<int, int>> ps{ { y, xs[y] } };
                    bool all = true;
                    for (int i = 0; i < 2 && all; ++i) {
                        for (int j = ps.size() - 1; j < (int)ps.size(); ++j) {
                            auto p = edges[ps[j].first][ps[j].second][i];
                            if (p.first >= 0) {
                                if (xs[p.first] < p.second)
                                    all = false;
                                else
                                    ps.emplace_back(p);
                            }
                        }
                        reverse(ps.begin(), ps.end());
                    }
                    if (!all) break;
                    for (auto& p : ps) {
                        auto& step = paths[p.first][p.second];
                        for (int i = 0; i < (int)step.size(); i += 2)
                            cout << step[i + 1] + 1 << ' ' << step[i] + 1 << endl;
                        ++xs[p.first];
                    }
                    any = true;
                }
            }
            if (!any) break;
        }
    }

    void connect() {
        struct Solution {
            int score;
            int i;
            vector<Edge> edges;
            Solution() {}
            Solution(int score, int i, const vector<Edge>& edges) :
                score(score), i(i), edges(edges) {}
            bool operator < (const Solution& sol) const {
                return score < sol.score;
            }
        };
        vector<Solution> sols;
        int best_score = 1 << 30;
        for (int i = 0; i < KEEP; ++i) {
            auto edges = connect(best_sols[i], 2, best_scores[i] - best_score);
            sols.emplace_back(best_scores[i] - edges.size(), i, edges);
            best_score = min(best_score, sols.back().score);
        }
        sort(sols.begin(), sols.end());
        sols.resize(4);
        Solution best{ 1 << 30, 0, {} };
        for (auto& sol : sols) {
            auto edges = connect(best_sols[sol.i], 6, 0);
            if (sol.edges.size() < edges.size())
                sol = Solution(best_scores[sol.i] - edges.size(), sol.i, edges);
            best = min(best, sol);
        }
        print(best_sols[best.i], best.edges);
    }
}

int main() {
    timer.measure();
    Annealer::anneal();
    StepConnector::connect();
    return 0;
}

Submission Info

Judge Result