結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 kurenai3110
|
| 提出日時 | 2018-05-26 20:51:46 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 960 ms / 1,000 ms |
| コード長 | 7,850 bytes |
| コンパイル時間 | 35,168 ms |
| 実行使用メモリ | 1,752 KB |
| スコア | 47,381 |
| 最終ジャッジ日時 | 2018-05-26 20:52:22 |
|
ジャッジサーバーID （参考情報） |
judge7 / |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 |
ソースコード
#pragma GCC optimize "O3"
#pragma GCC target "avx"
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <chrono>
#include <bitset>
#include <cmath>
using namespace std;
const int TIME = 1;
class Timer {
chrono::high_resolution_clock::time_point start, end;
double limit;
public:
Timer() {
start = chrono::high_resolution_clock::now();
}
Timer(double l) {
start = chrono::high_resolution_clock::now();
limit = l;
}
double getTime() {
end = chrono::high_resolution_clock::now();
return chrono::duration<double>(end - start).count();
}
bool Over() {
if (getTime() > limit) {
return true;
}
return false;
}
void setLimit(double l) {
limit = l;
}
void setStart() { start = chrono::high_resolution_clock::now(); }
double getLimit() { return limit; }
};
class Xor128 {
unsigned static int x, y, z, w;
public:
Xor128() {
x = 31103110, y = 123456789, z = 521288629, w = 88675123;
}
unsigned int rand()
{
unsigned int t;
t = (x ^ (x << 11)); x = y; y = z; z = w;
return(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
};
unsigned int Xor128::x, Xor128::y, Xor128::z, Xor128::w;
const double TIMELIMIT = 0.95;
struct ANS {
char mode;
int r, c;
ANS(char mode = -1, int r = 0, int c = 0):mode(mode), r(r), c(c) {}
};
class Solver{
int N, K;
int L[500];
int oA[60][60];
int A[60][60];
int sumA0[61][61], sumA1[61][61];
Timer tmr;
Xor128 xor128;
vector<ANS>ans, best_ans;
int best_score;
public:
void input() {
cin >> N >> K;
for (int i = 0; i < K; i++)cin >> L[i];
for (int i = 0; i < N; i++)for (int j = 0; j < N; j++) {
char a; cin >> a; a -= '0';
oA[i][j] = a;
}
}
void init() {
tmr.setStart();
for (int i = 0; i < N; i++)for (int j = 0; j < N; j++)A[i][j] = oA[i][j];
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
sumA0[j][i] = sumA1[i][j] = 0;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sumA0[j][i + 1] += sumA0[j][i] + A[i][j];
sumA1[i][j + 1] += sumA1[i][j] + A[i][j];
}
}
ans.assign(K, ANS());
best_score = 0;
tmr.setLimit(TIMELIMIT);
}
void SA() {
double startTemp = 1.6, endTemp = 0.02;
double diffTemp = (endTemp - startTemp) / TIMELIMIT;
double current_time = tmr.getTime();
int score = best_score;
bool mode2 = false;
int loop = 0;
int i = 0;
while (current_time < TIMELIMIT) {
i = (i + 1) % K;
loop++;
if (loop % 10000 == 0) {
current_time = tmr.getTime();
if (mode2 == false && 6.*TIMELIMIT > 20.*(TIMELIMIT - current_time)) {
mode2 = true;
}
}
if (L[i] * TIMELIMIT < 20.*(TIMELIMIT - current_time))continue;
int tmp2 = 0;
if (ans[i].mode != -1) {
int r = ans[i].r;
int c = ans[i].c;
int mode = ans[i].mode;
if (mode) tmp2 += (sumA1[r][c + L[i]] - sumA1[r][c]);
else tmp2 += (sumA0[c][r + L[i]] - sumA0[c][r]);
tmp2 *= 2;
tmp2 -= L[i];
}
if (mode2 == false && L[i] > 4) {
if (tmp2 < -0.5*L[i])continue;
}
int change = -1e9;
bool mode;
int r, c;
for (int t = 0; t < L[i] + 2; t++) {
bool tmode = xor128.rand() % 2;
int tr = xor128.rand() % (N - L[i] + 1);
int tc = xor128.rand() % N;
if (tmode)swap(tr, tc);
if (t == 0) {
tmode = ans[i].mode;
tr = ans[i].r;
tc = ans[i].c;
if (tmode) {
tc -= xor128.rand() % 4 + 1;
if (tc < 0)continue;
}
else {
tr -= xor128.rand() % 4 + 1;
if (tr < 0)continue;
}
}
else if (t == 1) {
tmode = ans[i].mode;
tr = ans[i].r;
tc = ans[i].c;
if (tmode) {
tc += xor128.rand() % 4 + 1;
if (tc >= (N - L[i] + 1))continue;
}
else {
tr += xor128.rand() % 4 + 1;
if (tr >= (N - L[i] + 1))continue;
}
}
int tmp = scoring(tmode, tr, tc, i) + tmp2;
if (t < 2) if (mode2 == false && UINT32_MAX *0.45 > xor128.rand() )continue;
if (tmp >= change) {
mode = tmode;
r = tr;
c = tc;
change = tmp;
}
}
bool accept = false;
if (change >= 0)accept = true;
else if (change < -2)accept = false;
else {
double temp = startTemp + diffTemp * tmr.getTime();
double prob = exp(change / temp);
accept = prob * UINT32_MAX > xor128.rand();
}
if (accept) {
score += change;
if(ans[i].mode!=-1)update(ans[i].mode, ans[i].r, ans[i].c, i);
ans[i].mode = mode;
ans[i].r = r;
ans[i].c = c;
update(mode, r, c, i);
if (score > best_score) {
best_score = score;
best_ans = ans;
}
}
}
cerr << tmr.getTime() << endl;
cerr << loop << endl;
cerr << best_score << endl;
}
int scoring(bool mode, int r, int c, int i) {
int change = 0;
int* sA;
if (mode)sA = sumA1[r];
else sA = sumA0[c];
if (mode) change += (sA[c + L[i]] - sA[c]);
else change += (sA[r + L[i]] - sA[r]);
change -= L[i];
int r1, r2;
r1 = r; r2 = ans[i].r;
int c1, c2;
c1 = c; c2 = ans[i].c;
if (mode == ans[i].mode) {
if (mode == true && r1 == r2) {
if (c1 > c2)swap(c1, c2);
if (c1 + L[i] > c2)change += ((c1 + L[i] - c2) - 2 * (sA[c1 + L[i]] - sA[c2]));
}
if (mode == false && c1 == c2) {
if (r1 > r2)swap(r1, r2);
if (r1 + L[i] > r2)change += ((r1 + L[i] - r2) - 2 * (sA[r1 + L[i]] - sA[r2]));
}
}
else if (ans[i].mode != -1) {
if (mode) {
if (c1 <= c2 && c2 <= c1 + L[i] - 1 && r2 <= r1 && r1 <= r2 + L[i] - 1) {
change -= (A[r1][c2] ? 1 : -1);
}
}
else {
if (r1 <= r2 && r2 <= r1 + L[i] - 1 && c2 <= c1 && c1 <= c2 + L[i] - 1) {
change -= (A[r2][c1] ? 1 : -1);
}
}
}
change *= 2;
change += L[i];
return change;
}
void update(bool mode, int r, int c, int i) {
if (mode) {
int p = 0;
if (N - c - L[i] + 1 < c) {
for (int j = c; j < c + L[i]; j++) {
sumA1[r][j] += p;
int p2 = (A[r][j] ? -1 : 1);
if (2 * r < N) for (int k = r; k >= 0; k--)sumA0[j][k] -= p2;
else for (int k = r + 1; k <= N; k++)sumA0[j][k] += p2;
p += (A[r][j] ? -1 : 1);
A[r][j] ^= 1;
}
if (p) for (int j = c + L[i]; j <= N; j++)sumA1[r][j] += p;
}
else {
for (int j = c + L[i] - 1; j >= c; j--) {
int p2 = (A[r][j] ? -1 : 1);
if (2 * r < N) for (int k = r; k >= 0; k--)sumA0[j][k] -= p2;
else for (int k = r + 1; k <= N; k++)sumA0[j][k] += p2;
p += (A[r][j] ? -1 : 1);
A[r][j] ^= 1;
sumA1[r][j] -= p;
}
if (p) for (int j = c - 1; j >= 0; j--)sumA1[r][j] -= p;
}
}
else {
int p = 0;
if (N - r - L[i] + 1 < r) {
for (int j = r; j < r + L[i]; j++) {
sumA0[c][j] += p;
int p2 = (A[j][c] ? -1 : 1);
if (2 * r < N) for (int k = c; k >= 0; k--)sumA1[j][k] -= p2;
else for (int k = c + 1; k <= N; k++)sumA1[j][k] += p2;
p += (A[j][c] ? -1 : 1);
A[j][c] ^= 1;
}
if (p)for (int j = r + L[i]; j <= N; j++) sumA0[c][j] += p;
}
else {
for (int j = r + L[i] - 1; j >= r; j--) {
int p2 = (A[j][c] ? -1 : 1);
if (2 * r < N) for (int k = c; k >= 0; k--)sumA1[j][k] -= p2;
else for (int k = c + 1; k <= N; k++)sumA1[j][k] += p2;
p += (A[j][c] ? -1 : 1);
A[j][c] ^= 1;
sumA0[c][j] -= p;
}
if (p)for (int j = r - 1; j >= 0; j--) sumA0[c][j] -= p;
}
}
}
void output() {
for (int i = 0; i < K; i++) {
cout << best_ans[i].r + 1 << " " << best_ans[i].c + 1 << " ";
if (best_ans[i].mode)cout << best_ans[i].r + 1 << " " << best_ans[i].c + L[i] << endl;
else cout << best_ans[i].r + L[i] << " " << best_ans[i].c + 1 << endl;
}
}
int run() {
init();
SA();
output();
return best_score;
}
};
int main() {
Solver slv;
slv.input();
double ave_score = 0;
for (int t = 0; t < TIME; t++) {
ave_score += slv.run();
}
cerr << 1. * ave_score / TIME << endl;
return 0;
}