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

提出ソース

結果

問題	No.5002 stick xor
ユーザー	kosakkun
提出日時	2018-05-26 01:40:04
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	973 ms / 1,000 ms
コード長	6,066 bytes
コンパイル時間	35,831 ms
実行使用メモリ	1,632 KB
スコア	41,301
最終ジャッジ日時	2018-05-26 01:40:45
ジャッジサーバーID （参考情報）	judge6 /
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

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

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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.8;
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;
int Answer[500][4];
int 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 = CurScore;
    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 - CurScore;
}

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

yukicoder

結果

テストケース

ソースコード