#262095 (C++11（廃止可能性あり）) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: machy
• 提出日時: 2018-06-01 21:53:28
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: AC
• 実行時間: 956 ms / 1,000 ms
• コード長: 12,147 bytes
• コンパイル時間: 33,873 ms
• 実行使用メモリ: 1,612 KB
• スコア: 43,943
• 最終ジャッジ日時: 2018-06-01 21:54:04
• ジャッジサーバーID （参考情報）: judge6 /

ファイルパターン	結果
other	AC * 32

ソースコード

#include <iostream>
#include <vector>
#include <cassert>
#include <random>
#include <string>

using namespace std;
#include <sys/time.h>

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

#include<vector>
#include<string>

template <typename T>
struct PointBase{
    T y, x;
    PointBase(T y_, T x_):y(y_),x(x_){}
    PointBase(){}
    bool operator<(const PointBase& op) const{
        if(this->y == op.y) return this->x < op.x;
        return this->y < op.y;
    }
    bool operator==(const PointBase& op) const{
        return this->y == op.y && this->x == op.x;
    }
    PointBase& operator+=(const PointBase& op){
        this->y += op.y; this->x += op.x;
        return *this;
    }
};
template <typename T> string to_string(const PointBase<T>& p){
    return string("(") + to_string(p.y) + "," + to_string(p.x) + ")";
}
template <typename T> std::ostream& operator<<(std::ostream& os, const PointBase<T>& p) {
    os << to_string(p);
    return os;
}
typedef PointBase<int> Point;


template <typename T>
struct BoardBase{
    int h, w;
    vector<T> data;
    BoardBase(int h_, int w_, const T& init):h(h_),w(w_),data(h * w, init){}
    void put(Point& p, const T& val){
        data[p.y*w + p.x] = val;
    }
    void put(int pos, const T& val){
        data[pos] = val;
    }
    void put(int y, int x, const T& val){
        data[y*w + x] = val;
    }
    T& get(Point& p){
        return data[p.y*w + p.x];
    }
    T& get(int pos){
        return data[pos];
    }
    T& get(int y, int x){
        return data[y*w + x];
    }
};
typedef BoardBase<int> Board;


typedef long long LL;

//*
mt19937 randint(123123123);
/*/
struct XORShift{
    uint32_t operator()(){
        static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;
        uint32_t t = x ^ (x << 11);
        x = y; y = z; z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }
} randint;
//*/

const int N = 60, K = 500;
vector<int> L;
Timer timer(0.95);

double componentCount(uint64_t val, uint64_t val_zero){
    uint64_t comp = (val ^ (val<<1)) & val;
    uint64_t bridge = val_zero & (val >> 1) & (val << 1);
    return __builtin_popcountll(comp) - __builtin_popcountll(bridge);
}

double componentCount(vector<uint64_t>& vec, vector<uint64_t>& vec_zero){
    double ans = 0;
    for(int i = 0; i < N; ++i){
        ans += componentCount(vec[i], vec_zero[i]);
    }
    return ans;
}

double componentCount(vector<uint64_t>& rows, vector<uint64_t>& cols, vector<uint64_t>& rows_zero, vector<uint64_t>& cols_zero){
    return componentCount(rows, rows_zero) + componentCount(cols, cols_zero);
}

double componentCountDiff(vector<uint64_t>& rows, vector<uint64_t>& cols, vector<uint64_t>& rows_zero, vector<uint64_t>& cols_zero, int y, int x){
    return componentCount(rows[y], rows_zero[y]) + componentCount(cols[x], cols_zero[x]);
}

struct State{
    vector<uint64_t> rows;
    vector<uint64_t> cols;
    vector<Point> assign;
    vector<bool> assign_row;
    vector<int> row_assign1;
    vector<int> col_assign1;
    int score;
    int last_cur, last_cur2;
    Point last_p, last_p2;
    bool last_is_row;
    State(vector<uint64_t>& rows_, vector<uint64_t>& cols_)
    :assign(K), assign_row(K), row_assign1(N, -1), col_assign1(N, -1){
        for(int i = 0; i < K; ++i){
            if(i % 2 == 0){
                assign[i] = Point(randint() % N, 0);
                assign_row[i] = true;
            }else{
                assign[i] = Point(0, randint() % N);
                assign_row[i] = false;
            }
        }
        reset(rows_, cols_);
    }
    void reset(vector<uint64_t>& rows_, vector<uint64_t>& cols_){
        rows = rows_;
        cols = cols_;
        score = 0;
        for(int cur = 0; cur < K; ++cur){
            Point p = assign[cur];
            if(assign_row[cur]){
                rows[p.y] ^= (1ULL << (p.x+L[cur])) - (1ULL << p.x);
            }else{
                cols[p.x] ^= (1ULL << (p.y+L[cur])) - (1ULL << p.y);
            }
        }
        for(int i = 0; i < N; ++i){
            score += __builtin_popcountll(rows[i]);
            score += __builtin_popcountll(cols[i]);
        }
    }
    vector<uint64_t> getRows(){
        vector<uint64_t> res(N);
        for(int cur = 0; cur < K; ++cur){
            Point p = assign[cur];
            if(assign_row[cur]){
                res[p.y] ^= (1ULL << (p.x+L[cur])) - (1ULL << p.x);
            }
        }
        return res;
    }
    vector<uint64_t> getCols(){
        vector<uint64_t> res(N);
        for(int cur = 0; cur < K; ++cur){
            Point p = assign[cur];
            if(!assign_row[cur]){
                res[p.x] ^= (1ULL << (p.y+L[cur])) - (1ULL << p.y);
            }
        }
        return res;
    }


    void place(int cur, int y, int x, int is_row){
        // undo info
        last_cur = cur;
        last_p = assign[cur];
        last_is_row = assign_row[cur];

        // unplace
        Point p = assign[cur];
        if(assign_row[cur]){
            score -= __builtin_popcountll(rows[p.y]);
            rows[p.y] ^= (1ULL << (p.x+L[cur])) - (1ULL << p.x);
            score += __builtin_popcountll(rows[p.y]);
        }else{
            score -= __builtin_popcountll(cols[p.x]);
            cols[p.x] ^= (1ULL << (p.y+L[cur])) - (1ULL << p.y);
            score += __builtin_popcountll(cols[p.x]);
        }

        // place
        if(is_row){
            row_assign1[y] = cur;
            assign[cur] = Point(y, x);
            assign_row[cur] = true;
            score -= __builtin_popcountll(rows[y]);
            rows[y] ^= (1ULL << (x+L[cur])) - (1ULL << x);
            score += __builtin_popcountll(rows[y]);
        }else{
            col_assign1[x] = cur;
            assign[cur] = Point(y, x);
            assign_row[cur] = false;
            score -= __builtin_popcountll(cols[x]);
            cols[x] ^= (1ULL << (y+L[cur])) - (1ULL << y);
            score += __builtin_popcountll(cols[x]);
        }
    }

    void place2(int cur, int y, int x, int cur2, int y2, int x2, int is_row){
        place(cur2, y2, x2, is_row);
        last_cur2 = last_cur;
        last_p2 = last_p;

        place(cur, y, x, is_row);
    }


    void undo(){
        place(last_cur, last_p.y, last_p.x, last_is_row);
    }
    void undo2(){
        place2(last_cur, last_p.y, last_p.x, last_cur2, last_p2.y, last_p2.x, last_is_row);
    }

    vector<pair<Point, Point>> getAssign() const{
        vector<pair<Point, Point>> res(K);
        for(int i = 0; i < K; ++i){
            res[i].first = assign[i];
            if(assign_row[i]){
                res[i].second = Point(assign[i].y + 1, assign[i].x + L[i]);
            }else{
                res[i].second = Point(assign[i].y + L[i], assign[i].x + 1);
            }
            assert(0 <= res[i].first.y && res[i].first.y < N);
            assert(0 <= res[i].first.x && res[i].first.x < N);
            assert(0 < res[i].second.y && res[i].second.y <= N);
            assert(0 < res[i].second.x && res[i].second.x <= N);
        }
        return res;
    }
    int getScore() const{ return score; }
};

int calcScore(vector<vector<int>>& board1, vector<vector<int>>& board2){
    int score = 0;
    for(int y = 0; y < N; ++ y){
        for(int x = 0; x < N; ++x){
            score += board1[y][x] - board2[y][x];
        }
    }
    return score;
}

vector<uint64_t> makeTargetRows(vector<vector<int>>& board, vector<uint64_t>& cols){
    vector<uint64_t> rows(N);
    for(int y = 0; y < N; ++y){
        for(int x = 0; x < N; ++x){
            if((board[y][x] ^ ((cols[x]>>y)&1)) == 1){
                rows[y] |= (1ULL << x);
            }
        }
    }
    return rows;
}

vector<uint64_t> makeTargetCols(vector<vector<int>>& board, vector<uint64_t>& rows){
    vector<uint64_t> cols(N);
    for(int y = 0; y < N; ++y){
        for(int x = 0; x < N; ++x){
            if((board[y][x] ^ ((rows[y]>>x)&1)) == 1){
                cols[x] |= (1ULL << y);
            }
        }
    }
    return cols;
}

vector<pair<Point, Point>> optimize(vector<vector<int>>& board){
    vector<uint64_t> cols(N);
    vector<uint64_t> rows = makeTargetRows(board, cols);
    State s(rows, cols);
    State best_s = s;

    double threshold_base = 6.0;
    int threshold = threshold_base;
    bool is_row = true;
    LL e = 0;
    for(; ; ++e){
        if((e & 0xfff) == 0xfff){
            threshold = threshold_base * (1.0 - timer.used());
            if(timer.timeup()) break;
            if(is_row){
                is_row = false;
                rows = s.getRows();
                cols = makeTargetCols(board, rows);
                s.reset(rows, cols);
            }else{
                is_row = true;
                cols = s.getCols();
                rows = makeTargetRows(board, cols);
                s.reset(rows, cols);
            }
        }
        int cur = randint() % K;
        if(s.assign_row[cur] != is_row) continue;
        int offset = randint() % (N+1 - L[cur]);
        int idx = randint() % N;
        if(randint() & 1){
            if(is_row){
                s.place(cur, idx, offset, true);
            }else{
                s.place(cur, offset, idx, false);
            }
            if(s.getScore()-threshold <= best_s.getScore()){
                if(s.getScore() < best_s.getScore()){
                    cerr << "update : " << best_s.getScore() << " -> " << s.getScore() << endl;
                    best_s = s;
                }
            }else{
                s.undo();
            }
        }else{
            int cur2 = -1;
            if(is_row){
                cur2 = s.row_assign1[idx];
            }else{
                cur2 = s.col_assign1[idx];
            }
            if(cur2 < 0) continue;
            if(cur == cur2) continue;
            int offset2 = s.assign[cur].x;
            if(offset2 + L[cur2] > N) offset2 = randint() % (N+1 - L[cur2]);

            if(is_row){
                s.place2(cur, idx, offset, cur2, s.assign[cur].y, offset2, true);
            }else{
                s.place2(cur, offset, idx, cur2, offset2, s.assign[cur].x, false);
            }
            if(s.getScore()-threshold <= best_s.getScore()){
                if(s.getScore() < best_s.getScore()){
                    cerr << "update : " << best_s.getScore() << " -> " << s.getScore() << endl;
                    best_s = s;
                }
            }else{
                s.undo2();
            }
        }
    }
    cerr << "epoch " << e << endl;
    return best_s.getAssign();
}


int main(){
    int N_, K_;
    cin >> N_ >> K_;
    assert(N == N_ && K == K_);
    L.resize(K);
    for(int i = 0; i < K; ++i){
        cin >> L[i];
    }
    vector<vector<int>> board(N, vector<int>(N));
    for(int y = 0; y < N; ++y){
        string s;
        cin >> s;
        for(int x = 0; x < N; ++x){
            board[y][x] = (s[x] == '1')? 1: 0;
        }
    }

    vector<pair<Point, Point>> assign = optimize(board);
    vector<vector<int>> ans_board = board;
    for(pair<Point, Point> p: assign){
        cout << p.first.y+1 << " " << p.first.x+1 << " " << p.second.y << " " << p.second.x << endl;
        for(int y = p.first.y; y < p.second.y; ++y){
            for(int x = p.first.x; x < p.second.x; ++x){
                ans_board[y][x] = 1 - ans_board[y][x];
            }
        }
    }
    int score = calcScore(board, ans_board);
    cerr << "Score = " << score << endl;
    
    return 0;
}