結果

問題 No.5002 stick xor
ユーザー machymachy
提出日時 2018-05-28 09:07:56
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 9,744 bytes
コンパイル時間 31,945 ms
実行使用メモリ 1,628 KB
スコア 7,984
最終ジャッジ日時 2018-05-28 09:08:29
ジャッジサーバーID
（参考情報） 		judge9 /
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 903 ms
1,628 KB
testcase_01 WA -
testcase_02 AC 904 ms
1,624 KB
testcase_03 AC 904 ms
1,628 KB
testcase_04 AC 903 ms
1,624 KB
testcase_05 AC 904 ms
1,628 KB
testcase_06 WA -
testcase_07 AC 904 ms
1,628 KB
testcase_08 AC 904 ms
1,628 KB
testcase_09 AC 904 ms
1,628 KB
testcase_10 WA -
testcase_11 RE -
testcase_12 AC 904 ms
1,628 KB
testcase_13 AC 904 ms
1,624 KB
testcase_14 AC 904 ms
1,620 KB
testcase_15 AC 903 ms
1,624 KB
testcase_16 WA -
testcase_17 AC 904 ms
1,624 KB
testcase_18 AC 903 ms
1,628 KB
testcase_19 AC 904 ms
1,624 KB
testcase_20 AC 904 ms
1,624 KB
testcase_21 AC 904 ms
1,628 KB
testcase_22 WA -
testcase_23 AC 904 ms
1,628 KB
testcase_24 AC 904 ms
1,628 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 904 ms
1,628 KB
testcase_28 AC 903 ms
1,628 KB
testcase_29 AC 904 ms
1,624 KB
testcase_30 AC 904 ms
1,628 KB
testcase_31 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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.9);

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

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

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

int 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;
    int score;
    int last_cur;
    Point last_p;
    bool last_is_row;
    State(vector<uint64_t>& rows_, vector<uint64_t>& cols_)
    :rows(rows_), cols(cols_), assign(K), assign_row(K){
        score = 0;
        for(int i = 0; i < K; ++i){
            assign[i] = Point(0, 0);
            assign_row[i] = true;
            rows[0] ^= (1ULL << (0+L[i])) - (1ULL << 0);
            score += __builtin_popcountll(rows[i]);
            score += __builtin_popcountll(cols[i]);
        }
    }
    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){
            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{
            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 undo(){
        place(last_cur, last_p.y, last_p.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);
            }
        }
        return res;
    }
    int getScore() const{ return score; }
};

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

    double threshold_base = 5.0;
    int threshold = threshold_base;
    for(LL e = 0; ; ++e){
        if((e & 0xff) == 0xff){
            threshold = 5.0 * (1.0 - timer.used());
            if(timer.timeup()) break;
        }
        uint32_t r = randint();
        bool is_row = (r & 1);
        int cur = (r >> 1) % N;
        int offset = randint() % (N+1 - L[cur]);
        if(is_row){
            int y = randint() % N;
            s.place(cur, y, offset, true);
        }else{
            int x = randint() % N;
            s.place(cur, offset, x, true);
        }
        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();
        }
    }
    return best_s.getAssign();
}


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

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<uint64_t> rows(N), cols(N);
    vector<uint64_t> rows_zero(N), cols_zero(N);
    vector<Point> one_index;
    for(int y = 0; y < N; ++y){
        for(int x = 0; x < N; ++x){
            if(board[y][x] == 1){
                rows[y] |= (1ULL << x);
                one_index.emplace_back(y, x);
            }else{
                rows_zero[y] |= (1ULL << x);
                cols_zero[x] |= (1ULL << y);
            }
        }
    }
    cerr << "comp cnt : " << componentCount(rows, cols, rows_zero, cols_zero) << endl;

    int comp_best = componentCount(rows, cols, rows_zero, cols_zero);
    int comp_score = comp_best;
    vector<uint64_t> rows_best = rows, cols_best = cols;
    LL max_e = 1000*1000*5;
    for(LL e = 0; e < max_e; ++e){
        int threshold = 5.0 * (max_e - e) / max_e;
        int r = randint() % one_index.size();
        int y = one_index[r].y;
        int x = one_index[r].x;
        int score_prev = componentCountDiff(rows, cols, rows_zero, cols_zero, y, x);
        rows[y] ^= (1ULL << x);
        cols[x] ^= (1ULL << y);
        int score_next = componentCountDiff(rows, cols, rows_zero, cols_zero, y, x);
        //cerr << comp_best << ", " << score << ", " << score - comp_best << endl;
        if(comp_score + score_next - score_prev - threshold <= comp_best){
            comp_score += score_next - score_prev;
            //assert(score == componentCount(rows, cols, rows_zero, cols_zero));
            if(comp_score < comp_best){
                comp_best = comp_score;
                cerr << comp_best << endl;
            }
        }else{
            rows[y] ^= (1ULL << x);
            cols[x] ^= (1ULL << y);
        }
    }

    vector<pair<Point, Point>> assign = optimize(rows, cols);
    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;
}
0