結果

問題 No.5002 stick xor
ユーザー kosakkunkosakkun
提出日時 2018-05-26 03:17:30
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 974 ms / 1,000 ms
コード長 6,725 bytes
コンパイル時間 34,793 ms
実行使用メモリ 1,620 KB
スコア 41,551
最終ジャッジ日時 2018-05-26 03:18:06
ジャッジサーバーID
（参考情報） 		judge9 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#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 = 0.80;
const double TEMP_END   = 0.01;
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 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);
            int diff = move_rect(i, sx, sy, sx + lx - 1, sy + ly - 1);
            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 < sx + lx; x++) {
                    for (int y = sy; y < sy + ly; y++) {
                        A[x][y] = !A[x][y];
                    }
                }
                Answer[i][0] = sx;
                Answer[i][1] = sy;
                Answer[i][2] = sx + lx - 1;
                Answer[i][3] = sy + ly - 1;
                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 max_score = -1e9;
        int sx = -1, sy = -1, lx = -1, ly = -1;
        for (int j = 0; j < 100; j++) {
            int rd = Random.rand() & 1;
            int lxt = rd ? 1 : L[i];
            int lyt = rd ? L[i] : 1;
            int sxt = Random.rand() % (N - lxt + 1);
            int syt = Random.rand() % (N - lyt + 1);
            int score_t = 0;
            for (int x = sxt; x < sxt + lxt; x++) {
                for (int y = syt; y < syt + lyt; y++) {
                    if (A[x][y]) {
                        score_t++;
                    } else {
                        score_t--;
                    }
                }
            }
            if (score_t > max_score) {
                max_score = score_t;
                sx = sxt;
                sy = syt;
                lx = lxt;
                ly = lyt;
            }
        }
        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;
}
0