Submission #1868128

---

Source Code Expand

#define NDEBUG
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cassert>
#include <iomanip>
#include <cmath>
#include <unordered_set>
#include <sys/time.h>

using namespace std;

uint32_t rand_gen(){ 
    static uint32_t x = 123456789, y = 362436069, z = 521288629;
    static uint32_t w = 88675123; 
    uint32_t t;
    t = x ^ (x << 11); x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
}
double rand_d(){ return rand_gen() / double(1LL<<32); }


class Timer{
protected:
    double startTime;
    double limit;
    bool alreadyTimeup;
public:
    Timer(double time_limit){ 
        set(time_limit);
    }
    void set(double time_limit){
        limit = time_limit;
        startTime = now();
        alreadyTimeup = false;
    }
    bool timeup(){
        if(alreadyTimeup) return true;
        if(now() - startTime > limit){
            alreadyTimeup = true;
            return true;
        }else{
            return false;
        }
    }
    double elapse(){
        return now() - startTime;
    }
    double used(){
        return elapse() / limit;
    }
protected:
    double now(){
        timeval tv;
        gettimeofday(&tv, 0);
        return tv.tv_sec + tv.tv_usec * 1e-6;
    }
};

#ifdef LOCAL
const double TIME_LIMIT = 10.0;
#else
const double TIME_LIMIT = 29.0;
#endif
Timer timer(TIME_LIMIT);


/* 呼称の取り決め
 * edge           ... 元のグラフHのエッジ
 * node, n        ... 元のグラフHで参照するノード番号
 * Board          ... 射影先の正方形のKing'sグラフG
 * repr           ... nodeに対応するBoard上の点の集合(represents)
 * Point, p       ... Board上の(y, x)で表現した座標
 * PointIndex, pi ... Board上の座標を整数で表したもの。番兵ありで。
 * r              ... 乱数
 * Model          ... すべての射影情報
 */
const int DIST_INFINITY = 1000*1000;
const int NONE_NODE = 1000*1000;
const int MAX_REF = 4; // ひとつのセルに詰め込めるreplの最大数
const int EMPTY = -1;
const int SENTINEL = -1000*1000;
typedef long long LL;
typedef vector<vector<int>> VVI;
typedef vector<int> VI;


struct Point{
    int y; int x;
    Point(){}
    Point(int y_, int x_):y(y_),x(x_){}
};
ostream& operator<<(ostream& os, const Point& op){
    os << "(" << op.y << "," << op.x << ")";  
    return os;  
}

template <typename T>
struct Matrix{
    int n;
    vector<T> data;

    Matrix(int n_, T init, T sentinel) :n(n_), data((n_+2)*(n_+2), sentinel){
        for(int y = 0; y < n; ++y) for(int x = 0; x < n; ++x) set(y, x, init);
    }
    int width() const{ return n; }
    T& operator[](int pi){ return data[pi]; }
    T operator[](int pi) const{return data[pi]; }
    T operator()(int y, int x) const{ return data[n+2 + y*(n+1) + x]; }
    T operator()(const Point& p) const{ return data[n+2 + p.y*(n+1) + p.x]; }
    void set(int y, int x, T v){ data[n+2 + y*(n+1) + x] = v; }
    void set(const Point& p, T v){ data[n+2 + p.y*(n+1) + p.x] = v; }
    int pointIndex(int y, int x) const{ return n+2 + y*(n+1) + x; }
    int pointIndex(const Point& p) const{ return n+2 + p.y*(n+1) + p.x; }
    Point indexPoint(int pi) const{
        int y = (pi - (n+2)) / (n+1);
        int x = (pi - (n+2)) % (n+1);
        return Point(y, x);
    }
    void add(const Matrix<T>& op){
        for(int i = n+2; i < (n+2)*(n+2); ++i) data[i] += op.data[i];
    }
};
typedef Matrix<int> IMatrix;
typedef Matrix<vector<int>> VIMatrix;


int countEdge(const VVI& edge){
    int total_edge = 0;
    for(int i = 0; i < edge.size(); ++i){
        total_edge += edge[i].size();
    }
    assert(total_edge % 2 == 0);
    total_edge /= 2;
    return total_edge;
}


void showBoard(const IMatrix& board, ostream& ost){
    for(int y = 0; y < board.width(); ++y){
        for(int x = 0; x < board.width(); ++x){
            ost << setw(3) << board(y, x) << " ";
        }
        ost << endl;
    }
}


void random_sampling(VI::iterator begin, VI::iterator end, int k){
    for(int i = 0; i < k; ++i){
        int r = rand_gen() % (end - begin - i);
        swap(*(begin + i), *(begin + i + r));
    }
}


vector<int> random_sampling(int n, int k){
    assert(k <= n);
    vector<int> res(n);
    for(int i = 0; i < n; ++i){ res[i] = i; }
    random_sampling(res.begin(), res.end(), k);
    res.resize(k);
    return res;
}


//スコアを部分計算するための補助情報
struct ScoreInfo2{
    bool violated;
    int total_edge;
    int total_get_edge;
    int total_repr_size;
    int V;
    IMatrix ref_cnt;
    IMatrix edge_mat;


    ScoreInfo2(const VVI& edge, const VVI& repr, int W)
    :ref_cnt(repr.size(), 0, 0)
    ,edge_mat(repr.size(), 0, 0){
        violated = false;
        total_edge = countEdge(edge);
        total_get_edge = 0;
        total_repr_size = 0;
        V = repr.size();
        for(int i = 0; i < edge.size(); ++i){
            for(int j = 0; j < edge[i].size(); ++j){
                edge_mat.set(i, edge[i][j], 1);
            }
        }
        calcScore(edge, repr, W);
    }


    void calcScore(const VVI& edge, const VVI& repr, int W){
        const int delta[] = {-(W+1)-1, -(W+1)+0, -(W+1)+1, -1, 1, (W+1)-1, (W+1)+0, (W+1)+1};
        total_repr_size = 0;
        for(int i = 0; i < repr.size(); ++i){
            total_repr_size += repr[i].size();
        }
        IMatrix board(W, EMPTY, SENTINEL);
        for(int i = 0; i < repr.size(); ++i){
            for(int j = 0; j < repr[i].size(); ++j){
                // reprの配置が重複しているので0点
                if(board[repr[i][j]] >= 0){
                    violated = true;
                    return;
                }
                board[repr[i][j]] = i;
            }
        }

        for(int y = 0; y < W; ++y){
            for(int x = 0; x < W; ++x){
                int pi = board.pointIndex(y, x);
                int n1 = board[pi];
                if(n1 < 0) continue;
                for(int d = 0; d < 8; ++d){
                    int n2 = board[pi + delta[d]];
                    if(n2 < 0 || n1 == n2) continue;
                    ref_cnt.set(n1, n2, ref_cnt(n1, n2) + 1);
                }
            }
        }
        for(int i = 0; i < edge.size(); ++i){
            for(int j = 0; j < edge[i].size(); ++j){
                if(ref_cnt(i, edge[i][j]) > 0) total_get_edge += edge_mat(i, edge[i][j]);
            }
        }
        assert(total_get_edge % 2 == 0);
        total_get_edge /= 2;
    }

    int score() const{
        if(violated) return 0;
        int val = 5000 - (total_repr_size - V) + total_get_edge * 100;
        if(total_get_edge == total_edge) val += 100000;
        return val;
    }

    int remove(const VVI& edge, const VVI& repr, int W, const IMatrix& board, const vector<pair<int,int>>& edit_list){
        //checkRefCount(board);
        const int delta[] = {-(W+1)-1, -(W+1)+0, -(W+1)+1, -1, 1, (W+1)-1, (W+1)+0, (W+1)+1};
        for(int i = 0; i < edit_list.size(); ++i){
            int pi = edit_list[i].first;
            int node1 = edit_list[i].second;
            assert(node1 >= 0 && node1 == board[pi]);

            for(int d = 0; d < 8; ++d){
                int node2 = board[pi + delta[d]];
                if(node2 < 0 || node1 == node2) continue;
                assert(ref_cnt(node1, node2) > 0 && ref_cnt(node2, node1) == ref_cnt(node1, node2));
                ref_cnt.set(node1, node2, ref_cnt(node1, node2) - 1);
                ref_cnt.set(node2, node1, ref_cnt(node2, node1) - 1);
                assert(ref_cnt(node1, node2) >= 0);
                if(ref_cnt(node1, node2) == 0){
                    //cerr << "remove " << node1 << " , " << node2 << " , " << edge_mat(node1, node2) << endl;
                    total_get_edge -= edge_mat(node1, node2);
                }
            }
        }

        total_repr_size -= edit_list.size();
        /*
        for(int i = 0; i < edit_list.size(); ++i){
            int pi = edit_list[i].first;
            board[pi] = EMPTY;
        }
        */
        return score();
    }


    void checkBoard(const IMatrix& board, const VVI& repr) const{
        IMatrix board2(board.width(), EMPTY, SENTINEL);
        for(int i = 0; i < repr.size(); ++i){
            for(int j = 0; j < repr[i].size(); ++j){
                board2[repr[i][j]] = i;
            }
        }
        for(int y = 0; y < board.width(); ++y){
            for(int x = 0; x < board.width(); ++x){
                assert(board(y, x) == board2(y, x));
            }
        }
    }

    void checkRefCount(const IMatrix& board) const{
        int W = board.width();
        const int delta[] = {-(W+1)-1, -(W+1)+0, -(W+1)+1, -1, 1, (W+1)-1, (W+1)+0, (W+1)+1};
        IMatrix ref_cnt2(V, 0, 0);
        for(int y = 0; y < W; ++y){
            for(int x = 0; x < W; ++x){
                int pi = board.pointIndex(y, x);
                int n1 = board[pi];
                if(n1 < 0) continue;
                for(int d = 0; d < 8; ++d){
                    int n2 = board[pi + delta[d]];
                    if(n2 < 0 || n1 == n2) continue;
                    ref_cnt2.set(n1, n2, ref_cnt2(n1, n2) + 1);
                }
            }
        }
        for(int y = 0; y < V; ++y){
            for(int x = 0; x < V; ++x){
                if(ref_cnt(y, x) != ref_cnt2(y, x)){
                    showBoard(board, cerr);
                    cerr << "ref cnt " << y << " , " << x << ", " << ref_cnt(y, x) << " , " << ref_cnt2(y, x) << endl;
                }
                assert(ref_cnt(y, x) == ref_cnt2(y, x));
            }
        }
    }
 
    int append(const VVI& edge, const VVI& repr, int W, const IMatrix& board, const vector<pair<int,int>>& edit_list){
        const int delta[] = {-(W+1)-1, -(W+1)+0, -(W+1)+1, -1, 1, (W+1)-1, (W+1)+0, (W+1)+1};
        //checkBoard(board, repr);
        /*
        for(int i = 0; i < edit_list.size(); ++i){
            int pi = edit_list[i].first;
            int node = edit_list[i].second;
            board[pi] = node;
        }
        */
        total_repr_size += edit_list.size();

        for(int i = 0; i < edit_list.size(); ++i){
            int pi = edit_list[i].first;
            int node1 = board[pi];
            assert(node1 >= 0);

            for(int d = 0; d < 8; ++d){
                int node2 = board[pi + delta[d]];
                if(node2 < 0 || node1 == node2) continue;
                if(ref_cnt(node1, node2) == 0){
                    total_get_edge += edge_mat(node1, node2);
                }
                ref_cnt.set(node1, node2, ref_cnt(node1, node2) + 1);
                ref_cnt.set(node2, node1, ref_cnt(node2, node1) + 1);
                assert(ref_cnt(node1, node2) > 0 && ref_cnt(node2, node1) == ref_cnt(node1, node2));
            }
        }
        //checkRefCount(board);

        return score();
    }
};
int calcScore2(VVI& edge, VVI& repr, int W){
    return ScoreInfo2(edge, repr, W).score();
}

void searchRemove(VI& vec, int val){
    for(int i = 0; i < vec.size(); ++i){
        if(vec[i] == val){
            vec[i] = vec[vec.size()-1];
            vec.pop_back();
            return;
        }
    }
}


void calcDistance(const IMatrix& board, const VVI& repr, IMatrix& dist_board, int start_node, int end_node){
    int W = board.width();
    const int delta[] = {-(W+1)-1, -(W+1)+0, -(W+1)+1, -1, 1, (W+1)-1, (W+1)+0, (W+1)+1};
    const int delta1[] = {-(W+1)-1, -(W+1)+1, (W+1)-1, (W+1)+1};
    const int delta2[] = {-(W+1)+0, -1, 1, (W+1)+0};
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    for(int i = 0; i < repr[start_node].size(); ++i){
        int pi = repr[start_node][i];
        for(int d = 0; d < 8; ++d){
            if(board[pi + delta[d]] == EMPTY || board[pi + delta[d]] == end_node){
                q.push(pair<int,int>(0, pi + delta[d]));
            }
        }
    }
    while(!q.empty()){
        int dist = q.top().first;
        int pi = q.top().second;
        q.pop();
        if(dist_board[pi] <= dist) continue;
        if(board[pi] != EMPTY && board[pi] != end_node) continue;
        assert(board.indexPoint(pi).x < W);
        assert(board.indexPoint(pi).y < W);
        assert(board.indexPoint(pi).x >= 0);
        assert(board.indexPoint(pi).y >= 0);
        dist_board[pi] = dist;
        if(board[pi] == start_node) break;
        for(int d = 0; d < 8; ++d){
            if(dist_board[pi + delta[d]] > dist+1) q.push(pair<int,int>(dist+1, pi + delta[d]));
        }
    }
}


void setRepr(IMatrix& board, VIMatrix& board_ref, VVI& repr, int node, int pi){
    int W = board.width();
    //cerr << "pi=" << pi << " , x=" << board.indexPoint(pi).x << " , y=" << board.indexPoint(pi).y << " / " << board.width() << endl;
    assert(board.indexPoint(pi).x < W);
    assert(board.indexPoint(pi).y < W);
    assert(board.indexPoint(pi).x >= 0);
    assert(board.indexPoint(pi).y >= 0);
    assert(board_ref[pi].empty());
    board[pi] = node;
    board_ref[pi].push_back(node);
    assert(node >= 0 && node < repr.size());
    repr[node].push_back(pi);
}


void drawLine(IMatrix& board, VIMatrix& board_ref, VVI& repr, int node1, int pi, int node2){
    int W = board.width();
    //const int delta[] = {-(W+1)-1, -(W+1)+0, -(W+1)+1, -1, 1, (W+1)-1, (W+1)+0, (W+1)+1};
    const int delta[] = {-(W+1)-1, -(W+1)+1, (W+1)-1, (W+1)+1, -(W+1)+0, -1, 1, (W+1)+0};
    IMatrix dist_board(W, DIST_INFINITY, DIST_INFINITY);
    calcDistance(board, repr, dist_board, node2, node1);
    if(dist_board[pi] == DIST_INFINITY) return; // 到達不可能
    while(true){
        //cerr << "node=" << node1 << " , pi=" << pi << " , " << board[pi] << " , " << board.indexPoint(pi).x << " , " << board.indexPoint(pi).y << " / " << W << " , " << dist_board[pi] << endl;
        assert(board.indexPoint(pi).x < W);
        assert(board.indexPoint(pi).y < W);
        assert(board.indexPoint(pi).x >= 0);
        assert(board.indexPoint(pi).y >= 0);
        if(board[pi] != node1){
            assert(board_ref[pi].empty());
            setRepr(board, board_ref, repr, node1, pi);
        }
        if(dist_board[pi] <= 0) break;
        for(int d = 0; d < 8; ++d){
            if(dist_board[pi] == dist_board[pi + delta[d]] + 1){
                pi += delta[d];
                break;
            }
        }
    }
    //cerr << "draw line finish" << endl;
}


void removeRepresent(IMatrix& board, VIMatrix& board_ref, VVI& edge, VVI& repr, int node){
    assert(node >= 0);
    assert(node < repr.size());
    for(int i = 0; i < repr[node].size(); ++i){
        int pi = repr[node][i];
        assert(board[pi] >= 0);
        board[pi] = EMPTY;
        searchRemove(board_ref[pi], node);
        assert(board_ref[pi].empty());
        if(board_ref[pi].empty()) board[pi] = EMPTY;
    }
    repr[node].resize(0);
}


void buildRepresent(IMatrix& board, VIMatrix& board_ref, VVI& edge, VVI& repr, int node, int pi){
    int W = board.width();
    for(int i = 0; i < edge[node].size(); ++i){
        int node2 = edge[node][i];
        //cerr << "draw line=" << node << " , " << i << " / " << edge[node].size() << endl;
        drawLine(board, board_ref, repr, node, pi, node2);
    }
    if(board[pi] == node){
        //cerr << "success least one" << endl;
    }else{
        assert(board[pi] == EMPTY);
        setRepr(board, board_ref, repr, node, pi);
        //cerr << "represent failed" << endl;
    }
    assert(board[pi] == node);
}


vector<pair<int,int> > pairNode(const VI& pi_list, int node){
    vector<pair<int,int>> res;
    for(int i = 0; i < pi_list.size(); ++i){
        res.emplace_back(pi_list[i], node);
    }
    return res;
}


int selectPositionRandom(const IMatrix& board){
    int W = board.width();
    while(true){
        int y = rand_gen() % W;
        int x = rand_gen() % W;
        int pi = board.pointIndex(y, x);
        if(board[pi] == EMPTY) return pi;
    }
}


int selectPositionByDist(const IMatrix& board, const VVI& repr, const VI& node_list){
    int W = board.width();
    IMatrix total_dist(W, 0, 0);
    for(int node : node_list){
        IMatrix dist_board(W, DIST_INFINITY, DIST_INFINITY);
        calcDistance(board, repr, dist_board, node, NONE_NODE);
        total_dist.add(dist_board);
    }
    int best_dist = DIST_INFINITY * (node_list.size()+1);
    int best_pi = -1;
    for(int y = 0; y < W; ++y){
        for(int x = 0; x < W; ++x){
            int pi = board.pointIndex(y, x);
            if(board[pi] != EMPTY) continue;
            if(total_dist[pi] < best_dist){
                best_dist = total_dist[pi];
                best_pi = pi;
            }
        }
    }
    assert(best_pi != -1);
    //cerr << "pi=" << best_pi << " , dist=" << best_dist << endl;
    return best_pi;
}


int optimize2(VVI& edge, VVI& ret_repr, int W){
    int V = edge.size();

    IMatrix board(W, EMPTY, SENTINEL);
    VIMatrix board_ref(W, VI(), VI());
    VVI repr(V);

    VI rand_pos;
    for(int i = 0; i < W*W; ++i){
        rand_pos.push_back(board.pointIndex(i/W, i%W));
    }
    random_sampling(rand_pos.begin(), rand_pos.end(), V);
    for(int i = 0; i < V; ++i){
        setRepr(board, board_ref, repr, i, rand_pos[i]);
    }
    //showBoard(board, cerr);

    ScoreInfo2 score_info(edge, repr, W);
    int best_score = score_info.score();
    
    for(LL e = 0; ; ++e){
        if(timer.timeup()) break;
        int node = rand_gen() % V;
        if(e < V) node = e;
        //int node = e % V;
        //cerr << "select node : " << node << endl;
        score_info.remove(edge, repr, W, board, pairNode(repr[node], node));
        removeRepresent(board, board_ref, edge, repr, node);
        //int pi = selectPositionRandom(board);
        int pi = selectPositionByDist(board, repr, edge[node]);
        buildRepresent(board, board_ref, edge, repr, node, pi);
        int score = score_info.append(edge, repr, W, board, pairNode(repr[node], node));
        if(score > best_score){
            best_score = score;
            ret_repr = repr;
        }
        //if(e % 100 == 99) cerr << e << " : " << score << endl;
    }
    //assert(score_info.score() == calcScore2(edge, repr, W));
    //showBoard(board, cerr);
    return best_score;
}



//=====================================================================================
// ここからanealing手法
//=====================================================================================


struct Bijection{
    VI map_data;
    VI inv_data;

    Bijection():map_data(0), inv_data(0){}
    Bijection(int n_, int k_):map_data(n_), inv_data(k_){}
    void reset(int n_, int k_){ VI(n_, EMPTY).swap(map_data); VI(k_, EMPTY).swap(inv_data); }
    const size_t size() const{ return map_data.size(); }
    int map(int i) const{ return map_data.at(i); }
    int inv(int i) const{ return inv_data.at(i); }
    void set(int i, int v){
        if(i >= 0) map_data.at(i) = v;
        inv_data.at(v) = i;
    }
};

//スコアを部分計算するための補助情報
struct ScoreInfo{
    int total_edge;
    int total_get_edge;
    int total_repr_size;
    int V;
    const VVI& edge;
    const VVI& component;
    const VVI& emb_edge;
    IMatrix edge_mat;


    ScoreInfo(const VVI& edge_, const VVI& component_, const VVI& emb_edge_, const Bijection& repr)
    :edge(edge_), component(component_), emb_edge(emb_edge_)
    ,edge_mat(edge.size(), 0, 0){
        total_edge = countEdge(edge);
        total_get_edge = 0;
        total_repr_size = 0;
        V = edge.size();
        for(int i = 0; i < edge.size(); ++i){
            for(int j = 0; j < edge[i].size(); ++j){
                edge_mat.set(i, edge[i][j], 1);
            }
        }
        countRef(repr);
    }


    void countRef(const Bijection& repr){
        for(int node1 = 0; node1 < V; ++node1){
            int repr1 = repr.map(node1);
            //cerr << repr1 << " , size=" << component[repr1].size() << ", edge=" << emb_edge[repr1].size() << endl;
            total_repr_size += component[repr1].size();
            for(int i = 0; i < emb_edge[repr1].size(); ++i){
                int repr2 = emb_edge[repr1][i];
                //cerr << "repr2=" << repr2 << endl;
                int node2 = repr.inv(repr2);
                if(node2 < 0) continue;
                //cerr << "node1=" << node1 << " , node2=" << node2 << endl;
                total_get_edge += edge_mat(node1, node2);
            }
        }
        assert(total_get_edge % 2 == 0);
        total_get_edge /= 2;
    }

    int score() const{
        int val = 5000 - (total_repr_size - V) + total_get_edge * 100;
        if(total_get_edge == total_edge) val += 100000;
        return val;
    }

    void decRef(Bijection& repr, int repr1){
        assert(repr1 >= 0);
        int node1 = repr.inv(repr1);
        if(node1 < 0) return;
        total_repr_size -= component[repr1].size();
        for(int i = 0; i < emb_edge[repr1].size(); ++i){
            int repr2 = emb_edge[repr1][i];
            int node2 = repr.inv(repr2);
            //if(node2 < 0) continue;
            total_get_edge -= edge_mat(node1, node2);
        }
    }

    void incRef(Bijection& repr, int repr1){
        assert(repr1 >= 0);
        int node1 = repr.inv(repr1);
        if(node1 < 0) return;
        total_repr_size += component[repr1].size();
        for(int i = 0; i < emb_edge[repr1].size(); ++i){
            int repr2 = emb_edge[repr1][i];
            int node2 = repr.inv(repr2);
            //if(node2 < 0) continue;
            total_get_edge += edge_mat(node1, node2);
        }
    }

    int swapGain(Bijection& repr, int n1, int repr1, int n2, int repr2){
        int gain = 0;
        for(int i = 0; i < emb_edge[repr1].size(); ++i){
            int to_repr = emb_edge[repr1][i];
            int to_node = repr.inv(to_repr);
            gain -= edge_mat(n1, to_node);
        }
        for(int i = 0; i < emb_edge[repr2].size(); ++i){
            int to_repr = emb_edge[repr2][i];
            int to_node = repr.inv(to_repr);
            gain -= edge_mat(n2, to_node);
        }
        for(int i = 0; i < emb_edge[repr1].size(); ++i){
            int to_repr = emb_edge[repr1][i];
            int to_node = repr.inv(to_repr);
            gain += edge_mat(n2, to_node);
        }
        for(int i = 0; i < emb_edge[repr2].size(); ++i){
            int to_repr = emb_edge[repr2][i];
            int to_node = repr.inv(to_repr);
            gain += edge_mat(n1, to_node);
        }
        return gain * 100;
    }

    void swapRepr(Bijection& repr, int n1, int repr1, int n2, int repr2){
        decRef(repr, repr1);
        decRef(repr, repr2);
        repr.set(n1, repr2);
        repr.set(n2, repr1);
        incRef(repr, repr1);
        incRef(repr, repr2);
    }
};


void outputRepresent(const Bijection& repr, VVI& component, VVI& ret_repr){
    int V = repr.size();
    ret_repr.resize(0);
    for(int node = 0; node < repr.size(); ++node){
        ret_repr.push_back(component[repr.map(node)]);
    }
}

int twoSegmentCount(int height, int width){
    return (height + 1) / 2 * width;
}

void buildSegment(const IMatrix& board, VVI& component, int top, int left, int bottom, int right){
    if(top >= bottom) return;
    for(int x = left; x < right; x += 2){
        VI cc;
        for(int y = top; y < bottom; ++y){
            int h = y - top;
            int x2 = x + h;
            if(x2 >= right) x2 = right - 1 + right - x2;
            if(x2 < left) continue;
            if(x2 >= right) continue;
            cc.emplace_back(board.pointIndex(y, x2));
        }
        assert(!cc.empty());
        component.push_back(cc);
    }
    for(int x = left+1; x < right; x += 2){
        VI cc;
        for(int y = top; y < bottom; ++y){
            int h = y - top;
            int x2 = x - h;
            if(x2 < left) x2 = left + (left - x2 - 1);
            if(x2 < left) continue;
            if(x2 >= right) continue;
            cc.emplace_back(board.pointIndex(y, x2));
        }
        assert(!cc.empty());
        component.push_back(cc);
    }
}

void buildTwoSegment(const IMatrix& board, VVI& component, int top, int left, int bottom, int right){
    for(int y = top; y < bottom; y += 2){
        buildSegment(board, component, y, left, min(y+2, bottom), right);
    }
}

int isAdjasent(const VI& c1, const VI& c2, int W){
    const int delta[] = {-(W+1)-1, -(W+1)+0, -(W+1)+1, -1, 1, (W+1)-1, (W+1)+0, (W+1)+1};
    unordered_set<int> c2_set;
    for(int i = 0; i < c2.size(); ++i){
        c2_set.insert(c2[i]);
    }
    for(int i = 0; i < c1.size(); ++i){
        for(int d = 0; d < 8; ++d){
            int pi = c1[i] + delta[d];
            if(c2_set.count(pi) > 0) return true;
        }
    }
    return false;
}


void initializeBoard(int V, int W, Bijection& repr, VVI& component, VVI& emb_edge, int method){
    IMatrix board(W, EMPTY, SENTINEL);
    const int delta[] = {-(W+1)-1, -(W+1)+0, -(W+1)+1, -1, 1, (W+1)-1, (W+1)+0, (W+1)+1};
    // 周りに帯がおけるか判定
    int minW = W;
    bool around_flag = (W >= 4) && (twoSegmentCount(W-4, W-4) + 8 >= V);
    if(around_flag){
        cerr << "around" << endl;
        // left-top, bottom-right
        VI cc1, cc2, cc3, cc4;
        for(int y = 0; y < W-2; ++y){
            cc1.emplace_back(board.pointIndex(y, y%2));
            cc2.emplace_back(board.pointIndex(y, 1-y%2));
            cc3.emplace_back(board.pointIndex(W-1-y, W-1-y%2));
            cc4.emplace_back(board.pointIndex(W-1-y, W-1-(1-y%2)));
        }
        component.push_back(cc1);
        component.push_back(cc2);
        component.push_back(cc3);
        component.push_back(cc4);
        // right-top, bottom-left
        VI cc5, cc6, cc7, cc8;
        for(int x = 0; x < W-2; ++x){
            cc5.emplace_back(board.pointIndex(W-1-x%2, x));
            cc6.emplace_back(board.pointIndex(W-1-(1-x%2), x));
            cc7.emplace_back(board.pointIndex(x%2, W-1-x));
            cc8.emplace_back(board.pointIndex((1-x%2), W-1-x));
        }
        component.push_back(cc5);
        component.push_back(cc6);
        component.push_back(cc7);
        component.push_back(cc8);
    }else{
        cerr << "no around" << endl;
    }

    if(around_flag && W <= 4){
    }else if(around_flag){
        int seg_cnt = (V-8 + (W-4-1)) / (W-4);
        if(seg_cnt > W/2 || method == 1){
            cerr << "method1!********" << endl;
            for(int seg = 0; seg < seg_cnt; ++seg){
                int upper = 2 + (W-4) * seg / seg_cnt;
                int lower = 2 + (W-4) * (seg+1) / seg_cnt;
                buildSegment(board, component, upper, 2, lower, W-2);
            }
        }else{
            cerr << "method0!********" << endl;
            int seg_two_upper = (seg_cnt-1) / 2;
            int seg_two_lower = (seg_cnt-1) - seg_two_upper;
            buildTwoSegment(board, component, 2, 2, 2 + seg_two_upper*2, W-2);
            buildSegment(board, component, 2 + seg_two_upper*2, 2, W-2-seg_two_lower*2, W-2);
            buildTwoSegment(board, component, W-2-seg_two_lower*2, 2, W-2, W-2);
        }
    }else{
        int seg_cnt = (V + (W-1)) / W;
        for(int seg = 0; seg < seg_cnt; ++seg){
            int upper = W * seg / seg_cnt;
            int lower = W * (seg+1) / seg_cnt;
            buildSegment(board, component, upper, 0, lower, W);
        }
    }

/*
    // merge component
    for(int i = 0; i < 1000; ++i){
        if(component.size() <= V) break;
        if(V <= 10) break;
        int r = rand_gen() % (V-1);
        if(isAdjasent(component[r], component[r+1], W)){
            component[r].insert(component[r].end(), component[r+1].begin(), component[r+1].end());
            swap(component[r+1], component[component.size()-1]);
            component.pop_back();
        }
    }
    */
    
    // draw component
    for(int i = 0; i < component.size(); ++i){
        for(int j = 0; j < component[i].size(); ++j){
            assert(board[component[i][j]] == EMPTY);
            board[component[i][j]] = i;
        }
    }

    // collect edge
    emb_edge.resize(0);
    emb_edge.resize(component.size());
    for(int y = 0; y < W; ++y){
        for(int x = 0; x < W; ++x){
            int pi = board.pointIndex(y, x);
            int node1 = board[pi];
            if(node1 < 0) continue;
            for(int d = 0; d < 8; ++d){
                int node2 = board[pi + delta[d]];
                if(node2 < 0 || node2 == node1) continue;
                emb_edge[node1].emplace_back(node2);
            }
        }
    }
    for(int node = 0; node < component.size(); ++node){
        VI& vec = emb_edge[node];
        if(vec.empty()) continue;
        sort(vec.begin(), vec.end());
        int cnt = 1;
        for(int i = 1; i < vec.size(); ++i){
            if(vec[cnt-1] != vec[i]){
                vec[cnt] = vec[i];
                ++cnt;
            }
        }
        vec.resize(cnt);
    }

    //showBoard(board, cerr);
    cerr << "V=" << V << " , comp=" << component.size() << endl;
    assert(V <= component.size());
    repr.reset(V, component.size());
    for(int i = 0; i < V; ++i){ repr.set(i, i); }
}


int optimize(VVI& edge, VVI& ret_repr, int W, double time_begin, double time_target, int method){
    int V = edge.size();
    Bijection repr;
    VVI component;
    VVI emb_edge;
    initializeBoard(V, W, repr, component, emb_edge, method);
    ScoreInfo score_info(edge, component, emb_edge, repr);

    vector<pair<int,int>> edge_list;
    for(int i = 0; i < edge.size(); ++i){
        for(int j = 0; j < edge[i].size(); ++j){
            edge_list.emplace_back(i, edge[i][j]);
        }
    }

    double time_rate = (time_target - timer.used()) / (time_target - time_begin);
    LL e;
    for(e = 0; ; ++e){
        if((e & 0xfff) == 0){
            time_rate = (time_target - timer.used()) / (time_target - time_begin);
            if(time_rate <= 0.0) break;
        }
        int threshold = (rand_d() < (time_rate - 0.01) * 0.3)? 199: 0;

        int r = rand_gen() % edge_list.size();
        int n1 = edge_list[r].first;
        int n3 = edge_list[r].second;
        int repr1 = repr.map(n1);
        int repr3 = repr.map(n3);
        assert(!emb_edge[repr3].empty());
        int repr2 = emb_edge[repr3][rand_gen() % emb_edge[repr3].size()];
        if(repr1 == repr2) continue;
        int n2 = repr.inv(repr2);
        //cerr << "n1=" << n1 << " , n2=" << n2 << endl;
        int gain = score_info.swapGain(repr, n1, repr1, n2, repr2);
        if(gain + threshold >= 0){
            score_info.swapRepr(repr, n1, repr1, n2, repr2);
        }
        /*
        if(e % 10000 == 9999){
            cerr << e << " : " << score << " / " << best_score << endl;
        }
        */
    }
    cerr << "total epoch " << e << endl;
    outputRepresent(repr, component, ret_repr);
    return score_info.score();
}


void outputModel(VVI& repr, int W, ostream& ost){
    IMatrix board(W, EMPTY, SENTINEL);
    for(int i = 0; i < repr.size(); ++i){
        ost << repr[i].size();
        for(int j = 0; j < repr[i].size(); ++j){
            Point p = board.indexPoint(repr[i][j]);
            ost << " " << (p.y * board.width() + p.x +1);
        }
        ost << endl;
    }
}


int main(){
    int V, E;
    cin >> V >> E;
    VVI edge(V);

    for(int i = 0; i < E; ++i){
        int u, v;
        cin >> u >> v;
        --u; --v;
        edge[u].emplace_back(v);
        edge[v].emplace_back(u);
    }

    int Vemb, Eemb;
    cin >> Vemb >> Eemb;
    for(int i = 0; i < E; ++i){
        int a, b;
        cin >> a >> b;
    }
    int W = 0;
    for(; W*W < Vemb; ++W){
    }
    for(int i = 0; i < V; ++i){
        cerr << edge[i].size() << " ";
    }
    cerr << endl;
    cerr << "V=" << V << ", E=" << E << ", edge dencity=" << 100.0 * E / (V*(V+1)) << endl;
    cerr << "Vemb=" << Vemb << ", width=" << W << ", board dencity=" << 100.0 * V / Vemb << endl;

    VVI repr3(V), repr2(V), repr1(V);
    int score1 = optimize(edge, repr1, W, 0.00, 0.05, 0);
    int score3 = optimize(edge, repr3, W, 0.05, 0.10, 1);
    if(score1 > score3){
        score1 = optimize(edge, repr1, W, 0.10, 0.80, 0);
    }else{
        score1 = optimize(edge, repr1, W, 0.10, 0.80, 1);
    }
    int score2 = optimize2(edge, repr2, W);
    VVI best_repr;
    int best_score = 0;
    if(score1 >= score2){
        best_repr = repr1;
        best_score = score1;
        cerr << "anealing method won by " << score1 << " - " << score2 << endl;
    }else{
        best_repr = repr2;
        best_score = score2;
        cerr << "graph method won by " << score2 << " - " << score1 << endl;
    }
    cerr << "Score = " << best_score << endl;

#ifdef LOCAL
    ofstream ost("output/last");
    outputModel(best_repr, W, ost);
#else
    outputModel(best_repr, W, cout);
#endif
    return 0;
}

Submission Info

Judge Result