Submission #810627

---

Source Code Expand

#ifndef LOCAL
#define NDEBUG
#endif
#include <algorithm>
#include <cassert>
#include <cmath>
#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 = 9500;
    long long t = 0;
    bool elapses() const {
        return time() - t > limit;
    }
    void measure() {
        t = time() - t;
        ++n;
    }
    void measure(const string& id) { // twice call pair
        ts[id].measure();
    }
    void print(const string& id = "TOTAL") {
        if (n % 2 && id == "TOTAL")
            measure();
        assert(n % 2 == 0);
        for (auto& p : ts)
            p.second.print(p.first);
        fprintf(stderr, "%9s: %4lld, %d\n", id.c_str(), t, n / 2);
        fflush(stderr);
    }
    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) {
        assert(b > 0);
        return next() % b;
    }
    int next(int a, int b) {
        return next(b - a) + a;
    }
    double nextDouble(double b = 1) {
        return b * next() / (1ll << 32);
    }
    double nextDouble(double a, double b) {
        return nextDouble(b - a) + a;
    }
    int operator() (int b) { // for random_shuffle()
        return next(b);
    }
} rando;

template <typename Score>
class Annealing {
    const long long START_TIME;
    const double DIFF_COEF, FINAL_HEAT, INITIAL_HEAT, HEAT_COEF;
    Score th;
    double heat;
public:
    Annealing(double initialHeat, double finalHeat, int timeLimit, double diffCoef) :
        START_TIME(min(timer.time(), timer.t + timeLimit - 1)),
        DIFF_COEF(diffCoef),
        FINAL_HEAT(finalHeat),
        INITIAL_HEAT(max(FINAL_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)(heat * DIFF_COEF);
        return heat > FINAL_HEAT;
    }
    inline bool shouldTransit(Score diff) const {
        return diff < th && rando.nextDouble() < 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) {}
};

void print(vector<Node>& cells) {
    int i = 1;
    while (true) {
        for (; i < cells.size() && cells[i - 1].height < cells[i].height; ++i);
        int j = i - 1;
        while (i == cells.size() ? cells[i - 1].height : cells[i - 1].height >= cells[i].height) {
            for (; j - 1 >= 0 && cells[j - 1].height && cells[j].height - cells[j - 1].height == 1; --j);
            for (; j < i && cells[j].height == 0; ++j);
            for (int k = i - 1; k >= j; --k) {
                --cells[k].height;
                cout << cells[k].y + 1 << ' ' << cells[k].x + 1 << endl;
            }
        }
        if (i == cells.size()) break;
    }
}

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 - n1->forward + n2->height;
}

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

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 manhattan(Node* n1, Node* n2) {
    return abs(n1->x - n2->x) + abs(n1->y - n2->y);
}

void update(Node* b, Node* e) {
    b->prev = e->next = nullptr;
    b->begin = b;
    b->end = e;
    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);
}

bool tryTransit(Node* n1, Node* n2) {
    if (n1->prev == n2 || n1->next == n2) {
        if (n1->prev == n2)
            swap(n1, n2);
        int s1 = eval(n1);
        int s2 = eval1(n1->begin, n1) + eval1(n2, n2->end);
        if (s1 > s2) {
            update(n1->begin, n1);
            update(n2, n2->end);
            return true;
        }
    } else if (n1->prev && n1->next && n2->prev && n2->next) {
        if (n1->begin == n2->begin)
            return false;
        int s1 = eval(n1) + eval(n2);
        if (manhattan(n1->prev, n2->prev) == 1) {
            int s2 = evalfr(n1->prev, n2->prev) + evalrf(n1, n2);
            if (s1 > s2) {
                updatefr(n1->begin, n1->prev, n2->prev, n2->begin);
                updaterf(n1->end, n1, n2, n2->end);
                return true;
            }
        } else if (manhattan(n1->prev, n2->next) == 1) {
            int s2 = evalff(n1->prev, n2->next) + evalff(n2, n1);
            if (s1 > s2) {
                updateff(n1->begin, n1->prev, n2->next, n2->end);
                updateff(n2->begin, n2, n1, n1->end);
                return true;
            }
        } else if (manhattan(n1->next, n2->prev) == 1) {
            int s2 = evalff(n2->prev, n1->next) + evalff(n1, n2);
            if (s1 > s2) {
                updateff(n2->begin, n2->prev, n1->next, n1->end);
                updateff(n1->begin, n1, n2, n2->end);
                return true;
            }
        } else if (manhattan(n1->next, n2->next) == 1) {
            int s2 = evalrf(n1->next, n2->next) + evalfr(n1, n2);
            if (s1 > s2) {
                updaterf(n1->end, n1->next, n2->next, n2->end);
                updatefr(n1->begin, n1, n2, n2->begin);
                return true;
            }
        }
    } else if (n1->prev && n1->next || n2->prev && n2->next) {
        if (n1->prev && n1->next)
            swap(n1, n2);
        if (n1->begin != n2->begin) {
            int s1 = eval(n1) + eval(n2);
            int s2 = (n1->next ? n1->reverse : n1->forward) + diff(n1, n2);
            int s3 = diff(n2, n1) + (n1->next ? evalf(n1) : evalr(n1));
            int s4 = min(s2 + evalr(n2, n2->begin), n2->forward + s3) + eval1(n2->next, n2->end);
            int s5 = min(s2 + evalf(n2, n2->end), n2->reverse + s3) + eval1(n2->begin, n2->prev);
            if (s1 > s4 && s5 > s4) {
                update(n2->next, n2->end);
                if (n1->next)
                    updateff(n2->begin, n2, n1, n1->end);
                else
                    updatefr(n2->begin, n2, n1, n1->begin);
                return true;
            } else if (s1 > s5) {
                update(n2->begin, n2->prev);
                if (n1->next)
                    updaterf(n1->end, n1, n2, n2->end);
                else
                    updateff(n1->begin, n1, n2, n2->end);
                return true;
            }
        } else {
            int s1 = eval(n1);
            if (n1->next) {
                int s2 = min(n2->reverse + diff(n2, n1) + evalf(n1, n2->prev),
                    n1->reverse - n2->prev->reverse + diff(n1, n2) + evalf(n2, n2->end));
                if (s1 > s2) {
                    updaterf(n2->end, n2, n1, n2->prev);
                    return true;
                }
            } else {
                int s2 = min(n2->forward + diff(n2, n1) + evalr(n1, n2->next),
                    n1->forward - n2->next->forward + diff(n1, n2) + evalr(n2, n2->begin));
                if (s1 > s2) {
                    updatefr(n2->begin, n2, n1, n2->next);
                    return true;
                }
            }
        }
    } else {
        if (n1->begin == n2->begin)
            return false;
        int s1 = eval(n1) + eval(n2);
        int s2 = min(eval(n1, n2), eval(n2, n1));
        if (s1 > s2) {
            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);
            }
            return true;
        }
    }
    return false;
}

using Score = int;

const int N = 30;
Node sol[N][N], bestSol[N][N];
Score score, bestScore;

Score eval(Node sol[][N]) {
    Score 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;
}

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;
        }
    }
}

void transit(Score diff) {
    score += diff;
    if (bestScore > score) {
        bestScore = score;
        copy(sol, bestSol);
    }
}

int main() {
    timer.measure();

    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < N; ++x) {
            int h;
            cin >> h;
            sol[y][x] = bestSol[y][x] = { x, y, h };
            sol[y][x].begin = sol[y][x].end = &sol[y][x];
            bestSol[y][x].begin = bestSol[y][x].end = &bestSol[y][x];
        }
    }
    score = bestScore = eval(sol);

    // annealing
    Annealing<Score> sa(
        45500,
        0.7,
        9400,
        7
    );
    int ANNEAL = -1;
    while (++ANNEAL & 0x7ffff || sa.cool()) {
        // select randomly adjacent two cells
        Node* n1, * n2;
        unsigned r = rando.next();
        if (r & 0x8000) {
            int x = (r & 0x7fff) % (N - 1) + 1;
            int y = (r >> 17) % N;
            n1 = &sol[y][x - 1];
            n2 = &sol[y][x];
        } else {
            int x = (r & 0x7fff) % N;
            int y = (r >> 17) % (N - 1) + 1;
            n1 = &sol[y - 1][x];
            n2 = &sol[y][x];
        }

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

        // neighbor2 split and combine two paths
        } else if (n1->prev && n1->next && n2->prev && n2->next) {
            if (n1->begin == n2->begin) continue;
            int s1 = eval(n1) + eval(n2);
            if (manhattan(n1->prev, n2->prev) == 1) {
                int s2 = evalfr(n1->prev, n2->prev) + evalrf(n1, n2);
                Score diff = s2 - s1;
                if (sa.shouldTransit(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 s2 = evalff(n1->prev, n2->next) + evalff(n2, n1);
                Score diff = s2 - s1;
                if (sa.shouldTransit(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 s2 = evalff(n2->prev, n1->next) + evalff(n1, n2);
                Score diff = s2 - s1;
                if (sa.shouldTransit(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 s2 = evalrf(n1->next, n2->next) + evalfr(n1, n2);
                Score diff = s2 - s1;
                if (sa.shouldTransit(diff)) {
                    updaterf(n1->end, n1->next, n2->next, n2->end);
                    updatefr(n1->begin, n1, n2, n2->begin);
                    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 s1 = eval(n1) + eval(n2);
                int s2 = (n1->next ? n1->reverse : n1->forward) + diff(n1, n2);
                int s3 = diff(n2, n1) + (n1->next ? evalf(n1) : evalr(n1));
                if (r & 0x10000) {
                    int s4 = min(s2 + evalr(n2, n2->begin), n2->forward + s3) + eval1(n2->next, n2->end);
                    Score diff = s4 - s1;
                    if (sa.shouldTransit(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 s5 = min(s2 + evalf(n2, n2->end), n2->reverse + s3) + eval1(n2->begin, n2->prev);
                    Score diff = s5 - s1;
                    if (sa.shouldTransit(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 s1 = eval(n1);
                if (n1->next) {
                    int s2 = min(n2->reverse + diff(n2, n1) + evalf(n1, n2->prev),
                        n1->reverse - n2->prev->reverse + diff(n1, n2) + evalf(n2, n2->end));
                    Score diff = s2 - s1;
                    if (sa.shouldTransit(diff)) {
                        updaterf(n2->end, n2, n1, n2->prev);
                        transit(diff);
                    }
                } else {
                    int s2 = min(n2->forward + diff(n2, n1) + evalr(n1, n2->next),
                        n1->forward - n2->next->forward + diff(n1, n2) + evalr(n2, n2->begin));
                    Score diff = s2 - s1;
                    if (sa.shouldTransit(diff)) {
                        updatefr(n2->begin, n2, n1, n2->next);
                        transit(diff);
                    }
                }
            }

        // neighbor5 combine two paths to one path
        } else {
            if (n1->begin == n2->begin) continue;
            int s1 = eval(n1) + eval(n2);
            int s2 = min(eval(n1, n2), eval(n2, n1));
            Score diff = s2 - s1;
            if (sa.shouldTransit(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);
            }
        }
    }
    copy(bestSol, sol);

    // hill climbing
    while (true) {
        bool any = false;
        for (int y = 0; y < N; ++y)
            for (int x = 1; x < N; ++x)
                any |= tryTransit(&sol[y][x - 1], &sol[y][x]);
        for (int y = 1; y < N; ++y)
            for (int x = 0; x < N; ++x)
                any |= tryTransit(&sol[y - 1][x], &sol[y][x]);
        if (!any) break;
    }

    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < N; ++x) {
            auto n = &sol[y][x];
            if (n != n->begin) continue;
            vector<Node> cells;
            if (evalf(n) < evalr(n)) {
                for (; n; n = n->next)
                    cells.emplace_back(*n);
            } else {
                for (n = n->end; n; n = n->prev)
                    cells.emplace_back(*n);
            }
            print(cells);
        }
    }
    return 0;
}

Submission Info

Judge Result