結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 973 ms
1,632 KB
testcase_01 AC 973 ms
1,632 KB
testcase_02 AC 972 ms
1,632 KB
testcase_03 AC 972 ms
1,588 KB
testcase_04 AC 973 ms
1,584 KB
testcase_05 AC 973 ms
1,636 KB
testcase_06 AC 972 ms
1,584 KB
testcase_07 AC 972 ms
1,588 KB
testcase_08 AC 973 ms
1,584 KB
testcase_09 AC 972 ms
1,636 KB
testcase_10 AC 973 ms
1,584 KB
testcase_11 AC 973 ms
1,640 KB
testcase_12 AC 973 ms
1,588 KB
testcase_13 AC 973 ms
1,584 KB
testcase_14 AC 973 ms
1,632 KB
testcase_15 AC 972 ms
1,588 KB
testcase_16 AC 973 ms
1,588 KB
testcase_17 AC 973 ms
1,584 KB
testcase_18 AC 972 ms
1,588 KB
testcase_19 AC 973 ms
1,584 KB
testcase_20 AC 973 ms
1,632 KB
testcase_21 AC 973 ms
1,636 KB
testcase_22 AC 973 ms
1,584 KB
testcase_23 AC 973 ms
1,632 KB
testcase_24 AC 972 ms
1,632 KB
testcase_25 AC 972 ms
1,588 KB
testcase_26 AC 972 ms
1,636 KB
testcase_27 AC 973 ms
1,584 KB
testcase_28 AC 972 ms
1,584 KB
testcase_29 AC 973 ms
1,632 KB
testcase_30 AC 972 ms
1,640 KB
testcase_31 AC 971 ms
1,584 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>
#include <cstring>
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.001;
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[4][500];
char BestAnswer[4][500];

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

bool accept (double diff, double temp) {
    if (diff >= 0) return true;
    if (diff < -5) return false;
    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[0][idx]; x <= Answer[2][idx]; x++) {
        for (int y = Answer[1][idx]; y <= Answer[3][idx]; 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[0][idx]; x <= Answer[2][idx]; x++) {
        for (int y = Answer[1][idx]; y <= Answer[3][idx]; 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[0][i]; x <= Answer[2][i]; x++) {
                    for (int y = Answer[1][i]; y <= Answer[3][i]; 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[0][i] = sx;
                Answer[1][i] = sy;
                Answer[2][i] = sx + lx - 1;
                Answer[3][i] = sy + ly - 1;
                CurScore += diff;
                if (BestScore < CurScore) {
                    BestScore = CurScore;
                    for (int j = 0; j < 4; j++) {
                        copy(Answer[j], Answer[j] + K, BestAnswer[j]);
                    }
                }
            }
        }
    }
    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[0][i] = sx;
        Answer[1][i] = sy;
        Answer[2][i] = sx + lx - 1;
        Answer[3][i] = 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 < 4; i++) {
        copy(Answer[i], Answer[i] + K, BestAnswer[i]);
    }
}

int main () {
    cin.tie(0);
    ios::sync_with_stdio(false);
    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[j][i] + 1 << (j != 3 ? " " : "\n");
        }
    }
    cerr << BestScore << endl;
    return 0;
}
0