結果

問題 No.5002 stick xor
ユーザー kosakkunkosakkun
提出日時 2018-05-26 01:40:04
言語 C++14
(gcc 13.3.0 + boost 1.87.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 /
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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.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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0