#260659 (C++14) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: kosakkun
• 提出日時: 2018-05-26 19:56:06
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 974 ms / 1,000 ms
• コード長: 7,592 bytes
• コンパイル時間: 34,671 ms
• 実行使用メモリ: 1,620 KB
• スコア: 14,537
• 最終ジャッジ日時: 2018-05-26 19:56:42
• ジャッジサーバーID （参考情報）: judge6 /

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	972 ms; 1,620 KB
testcase_01	AC	973 ms; 1,616 KB
testcase_02	AC	972 ms; 1,616 KB
testcase_03	AC	972 ms; 1,612 KB
testcase_04	AC	973 ms; 1,616 KB
testcase_05	AC	973 ms; 1,620 KB
testcase_06	AC	973 ms; 1,616 KB
testcase_07	AC	972 ms; 1,616 KB
testcase_08	AC	973 ms; 1,616 KB
testcase_09	AC	972 ms; 1,620 KB
testcase_10	AC	973 ms; 1,616 KB
testcase_11	AC	973 ms; 1,616 KB
testcase_12	AC	973 ms; 1,616 KB
testcase_13	AC	973 ms; 1,620 KB
testcase_14	AC	972 ms; 1,620 KB
testcase_15	AC	974 ms; 1,620 KB
testcase_16	AC	972 ms; 1,616 KB
testcase_17	AC	973 ms; 1,616 KB
testcase_18	AC	973 ms; 1,620 KB
testcase_19	AC	972 ms; 1,616 KB
testcase_20	AC	973 ms; 1,616 KB
testcase_21	AC	971 ms; 1,616 KB
testcase_22	AC	973 ms; 1,616 KB
testcase_23	AC	972 ms; 1,620 KB
testcase_24	AC	972 ms; 1,620 KB
testcase_25	AC	974 ms; 1,620 KB
testcase_26	AC	972 ms; 1,616 KB
testcase_27	AC	972 ms; 1,620 KB
testcase_28	AC	973 ms; 1,616 KB
testcase_29	AC	972 ms; 1,616 KB
testcase_30	AC	972 ms; 1,612 KB
testcase_31	AC	972 ms; 1,620 KB

ソースコード

#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

/*******************************************************************/

struct Timer {
    
    double CYCLE_PER_SEC = 2800000000.0;
    unsigned long long BEGIN_CYCLE = 0;
    
    Timer() {}
    Timer(double cycle) : CYCLE_PER_SEC(cycle) {}
    
    unsigned long long int getCycle() {
        unsigned int low, high;
        __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
        return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
    }
    
    void start(void) {
        BEGIN_CYCLE = getCycle();
    }
    
    double get_time(void) {
        return (double)(getCycle() - BEGIN_CYCLE) / CYCLE_PER_SEC;
    }
    
} timer;

struct XorShift {
    unsigned int x;
    XorShift () : x(2463534242U) {}
    unsigned int rand() {
        x ^= (x << 13);
        x ^= (x >> 17);
        x ^= (x << 5);
        return x;
    }
} Random;

/*******************************************************************/

const double TIME_LIMIT = 0.90;
const double TEMP_START = 1.00;
const double TEMP_END   = 0.0001;
const double TEMP_DIFF  = (TEMP_START - TEMP_END) / TIME_LIMIT;

int N,K;
int L[500];
bool OriA[60][60];
bool A[60][60];

int CurScore;
int BestScore;
char Answer[500][4];
char BestAnswer[500][4];

/*******************************************************************/

bool accept (double diff, double temp) {
    if (diff >= 0) return true;
    double P = exp(diff / temp) * 4294967295.0;
    return Random.rand() < P;
}

int move_rect (int idx, int a2, int b2, int c2, int d2) {
    int ScoreNxt = 0;
    for (int x = Answer[idx][0]; x <= Answer[idx][2]; x++) {
        for (int y = Answer[idx][1]; y <= Answer[idx][3]; y++) {
            if (!A[x][y]) {
                ScoreNxt--;
            } else {
                ScoreNxt++;
            }
            A[x][y] = !A[x][y];
        }
    }
    for (int x = a2; x <= c2; x++) {
        for (int y = b2; y <= d2; y++) {
            if (!A[x][y]) {
                ScoreNxt--;
            } else {
                ScoreNxt++;
            }
            A[x][y] = !A[x][y];
        }
    }
    for (int x = Answer[idx][0]; x <= Answer[idx][2]; x++) {
        for (int y = Answer[idx][1]; y <= Answer[idx][3]; y++) {
            A[x][y] = !A[x][y];
        }
    }
    for (int x = a2; x <= c2; x++) {
        for (int y = b2; y <= d2; y++) {
            A[x][y] = !A[x][y];
        }
    }
    return ScoreNxt;
}

void simulated_annealing () {
    int cnt = 0;
    while (true) {
        cnt ++;
        double cur_time = timer.get_time();
        double cur_temp = TEMP_START - TEMP_DIFF * cur_time;
        if (cur_time > TIME_LIMIT) break;
        for (int i = 0; i < K; i++) {
            int sx = -1, sy = -1, ex = -1, ey = -1;
            int add = (Random.rand() % 2) * (Random.rand() % 2 == 1 ? -1 : 1);
            int rd = Random.rand() % 3;
            if (rd == 0) {
                if (Answer[i][0] == Answer[i][2]) {
                    int nxt = add + Answer[i][0];
                    if (nxt >= N || nxt < 0) continue;
                    sx = nxt;
                    sy = Answer[i][1];
                    ex = nxt;
                    ey = Answer[i][3];
                } else {
                    int snxt = add + Answer[i][0];
                    int enxt = add + Answer[i][2];
                    if (snxt >= N || snxt < 0) continue;
                    if (enxt >= N || enxt < 0) continue;
                    sx = snxt;
                    sy = Answer[i][1];
                    ex = enxt;
                    ey = Answer[i][3];
                }
            } else if (rd == 1) {
                if (Answer[i][1] == Answer[i][3]) {
                    int nxt = add + Answer[i][1];
                    if (nxt >= N || nxt < 0) continue;
                    sx = Answer[i][0];
                    sy = nxt;
                    ex = Answer[i][2];
                    ey = nxt;
                } else {
                    int snxt = add + Answer[i][1];
                    int enxt = add + Answer[i][3];
                    if (snxt >= N || snxt < 0) continue;
                    if (enxt >= N || enxt < 0) continue;
                    sx = Answer[i][0];
                    sy = snxt;
                    ex = Answer[i][2];
                    ey = enxt;
                }
            } else {
                sx = Answer[i][2];
                sy = Answer[i][3];
                ex = Answer[i][0];
                ey = Answer[i][1];
            }
            int diff = move_rect(i, sx, sy, ex, ey);
            if (accept((double) diff, cur_temp)) {
                for (int x = Answer[i][0]; x <= Answer[i][2]; x++) {
                    for (int y = Answer[i][1]; y <= Answer[i][3]; y++) {
                        A[x][y] = !A[x][y];
                    }
                }
                for (int x = sx; x <= ex; x++) {
                    for (int y = sy; y <= ey; y++) {
                        A[x][y] = !A[x][y];
                    }
                }
                Answer[i][0] = sx;
                Answer[i][1] = sy;
                Answer[i][2] = ex;
                Answer[i][3] = ey;
                CurScore += diff;
                if (BestScore < CurScore) {
                    BestScore = CurScore;
                    for (int j = 0; j < K; j++) {
                        for (int k = 0; k < 4; k++) {
                            BestAnswer[j][k] = Answer[j][k];
                        }
                    }
                }
            }
        }
    }
    cerr << cnt << endl;
}

void initialize () {
    for (int i = 0; i < K; i++) {
        int rd = Random.rand() & 1;
        int lx = rd ? 1 : L[i];
        int ly = rd ? L[i] : 1;
        int sx = Random.rand() % (N - lx + 1);
        int sy = Random.rand() % (N - ly + 1);
        Answer[i][0] = sx;
        Answer[i][1] = sy;
        Answer[i][2] = sx + lx - 1;
        Answer[i][3] = sy + ly - 1;
        for (int x = sx; x < sx + lx; x++) {
            for (int y = sy; y < sy + ly; y++) {
                A[x][y] = !A[x][y];
            }
        }
    }
    int cnt_ori = 0, cnt_nxt = 0;
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            if (!OriA[x][y]) cnt_ori++;
            if (   !A[x][y]) cnt_nxt++;
        }
    }
    CurScore = cnt_nxt - cnt_ori;
    BestScore = CurScore;
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < 4; j++) {
            BestAnswer[i][j] = Answer[i][j];
        }
    }
}

int main () {
    timer.start();
    cin >> N >> K;
    for (int i = 0; i < K; i++) {
        cin >> L[i];
    }
    for (int i = 0; i < N; i++) {
        string line; cin >> line;
        for (int j = 0; j < N; j++) {
            if (line[j] == '1') {
                OriA[i][j] = A[i][j] = true;
            } else {
                OriA[i][j] = A[i][j] = false;
            }
        }
    }
    initialize();
    simulated_annealing();
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < 4; j++) {
            cout << BestAnswer[i][j] + 1 << (j != 3 ? " " : "\n");
        }
    }
    cerr << BestScore << endl;
    return 0;
}