結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 Hoi_koro
|
| 提出日時 | 2018-05-29 23:20:14 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 977 ms / 1,000 ms |
| コード長 | 10,139 bytes |
| コンパイル時間 | 35,114 ms |
| 実行使用メモリ | 1,700 KB |
| スコア | 51,325 |
| 最終ジャッジ日時 | 2018-05-29 23:20:51 |
|
ジャッジサーバーID （参考情報） |
judge7 / |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 |
ソースコード
#include <bits/stdc++.h>
#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif
using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;
namespace Problem {
using namespace std;
struct Rec {
int dir, // direction(0,horizontal, 1:vertical),
y, x; // coordinate left-upper corner
};
uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;
uint32_t xor128() {
uint32_t t = x ^ (x << 11);
x = y;
y = z;
z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
class Solver {
public:
int n, k;
vector<int> len;
vector<LL> grid;
vector<Rec> rec, ans;
random_device rnd;
mt19937 mt;
chrono::system_clock::time_point start = chrono::system_clock::now();
Solver(LL n, LL k) : n(n), k(k), len(k), grid(n, 0), rec(k), mt(rnd()){};
void calc_SA() {
double temp1 = 0.98, temp2 = 0.99, temp3 = 1.0;
int q, d, x, y;
int score = -evaluate(grid, rec), max_score;
double diff;
DBG(score)
for (int i = 0; i < k; ++i) {
d = xor128() % 2;
y = xor128() % n;
x = xor128() % (n - len[i] + 1);
if (d == 1) swap(x, y);
add_rectangle(grid, rec, i, d, y, x);
}
score += evaluate(grid, rec);
max_score = score;
ans = rec;
DBG(score)
int loop = 0;
while (!time_limit()) {
// cerr << temp3 << ' ' << score << endl;
for (int _ = 0; _ < 10000; ++_) {
// first
q = xor128() % k;
x = xor128() % 2 * 2 - 1;
if (rec[q].dir == 0) {
if (x == -1 and rec[q].x > 0) {
diff = (((grid[rec[q].y] >> (rec[q].x - 1)) & 1) +
((grid[rec[q].y] >> (rec[q].x + len[q] - 1)) & 1)) *
2 -
2;
if ((double)xor128() / (double)(1ll << 32) < exp(diff / temp1)) {
grid[rec[q].y] ^= (1ll << (rec[q].x - 1));
grid[rec[q].y] ^= (1ll << (rec[q].x + len[q] - 1));
rec[q].x--;
score += diff;
if (score > max_score) {
max_score = score;
ans = rec;
}
}
} else if (x == 1 and rec[q].x + len[q] < n) {
diff = (((grid[rec[q].y] >> (rec[q].x)) & 1) +
((grid[rec[q].y] >> (rec[q].x + len[q])) & 1)) *
2 -
2;
if ((double)xor128() / (double)(1ll << 32) < exp(diff / temp1)) {
grid[rec[q].y] ^= (1ll << (rec[q].x));
grid[rec[q].y] ^= (1ll << (rec[q].x + len[q]));
rec[q].x++;
score += diff;
if (score > max_score) {
max_score = score;
ans = rec;
}
}
}
} else {
if (x == -1 and rec[q].y > 0) {
diff = (((grid[rec[q].y - 1] >> (rec[q].x)) & 1) +
((grid[rec[q].y + len[q] - 1] >> (rec[q].x)) & 1)) *
2 -
2;
if ((double)xor128() / (double)(1ll << 32) < exp(diff / temp1)) {
grid[rec[q].y - 1] ^= (1ll << rec[q].x);
grid[rec[q].y + len[q] - 1] ^= (1ll << rec[q].x);
rec[q].y--;
score += diff;
if (score > max_score) {
max_score = score;
ans = rec;
}
}
} else if (x == 1 and rec[q].y + len[q] < n) {
diff = (((grid[rec[q].y] >> (rec[q].x)) & 1) +
((grid[rec[q].y + len[q]] >> (rec[q].x)) & 1)) *
2 -
2;
if ((double)xor128() / (double)(1ll << 32) < exp(diff / temp1)) {
grid[rec[q].y] ^= (1ll << rec[q].x);
grid[rec[q].y + len[q]] ^= (1ll << rec[q].x);
rec[q].y++;
score += diff;
if (score > max_score) {
max_score = score;
ans = rec;
}
}
}
}
// second : swap the length of two rectangles
q = xor128() % k;
do {
d = xor128() % k;
} while (rec[d].dir != rec[q].dir or
(rec[d].dir == 0 and rec[q].y == rec[d].y) or
(rec[d].dir == 1 and rec[q].x == rec[d].x));
if (len[q] < len[d]) swap(q, d);
diff = -2 * (len[q] - len[d]);
if (len[q] > len[d]) {
if (rec[d].dir == 0 and rec[d].x + len[q] <= n) {
LL mask = (1ll << len[q]) - (1ll << len[d]);
diff +=
__builtin_popcountll((mask << rec[q].x) & grid[rec[q].y]) * 2;
diff +=
__builtin_popcountll((mask << rec[d].x) & grid[rec[d].y]) * 2;
if ((double)xor128() / (double)(1ll << 32) < exp(diff / temp2)) {
score += diff;
grid[rec[q].y] ^= (mask << rec[q].x);
grid[rec[d].y] ^= (mask << rec[d].x);
swap(rec[q], rec[d]);
if (score > max_score) {
max_score = score;
ans = rec;
}
}
} else if (rec[d].dir == 1 and rec[d].y + len[q] <= n) {
for (int l = len[d]; l < len[q]; ++l) {
diff += ((grid[rec[q].y + l] >> (rec[q].x)) & 1) << 1;
diff += ((grid[rec[d].y + l] >> (rec[d].x)) & 1) << 1;
}
if ((double)xor128() / (double)(1ll << 32) < exp(diff / temp2)) {
score += diff;
for (int l = len[d]; l < len[q]; ++l) {
grid[rec[q].y + l] ^= (1ll << rec[q].x);
grid[rec[d].y + l] ^= (1ll << rec[d].x);
}
swap(rec[q], rec[d]);
if (score > max_score) {
max_score = score;
ans = rec;
}
}
}
}
// third
loop++;
q = xor128() % k;
d = xor128() % 2;
y = xor128() % n;
x = xor128() % (n - len[q] + 1);
if (d == 1) swap(x, y);
auto tmp = rec[q];
diff = remove_rectangle(grid, rec, q) +
add_rectangle(grid, rec, q, d, y, x);
if ((double)xor128() / (double)(1ll << 32) < exp(diff / temp3)) {
// DBG(score, diff)
score += diff;
if (score > max_score) {
max_score = score;
ans = rec;
}
} else {
remove_rectangle(grid, rec, q);
add_rectangle(grid, rec, q, tmp.dir, tmp.y, tmp.x);
}
}
DBG(temp1, score)
temp3 = update_temperature();
temp2 = 1.0 / (1.0 / temp3 + 0.004);
temp1 = 1.0 / (1.0 / temp2 + 0.004);
// temp2 = temp3 - pow(temp3, 2.01);
// temp1 = temp2 - pow(temp2, 2.02);
}
cerr << max_score << endl;
cerr << loop << endl;
}
int evaluate(vector<LL>& gr, vector<Rec>& r) {
int ret = n * n;
for (int i = 0; i < n; ++i) {
ret -= __builtin_popcountll(gr[i]);
}
return ret;
}
int remove_rectangle(vector<LL>& gr, vector<Rec>& r, int i) {
int ret = 0;
int yy = r[i].y;
int xx = r[i].x;
if (r[i].dir == 1) {
for (int j = 0; j < len[i]; ++j) {
ret += ((gr[yy] >> xx) & 1);
gr[yy] ^= (1ll << xx);
yy++;
}
} else {
LL mask = (1ll << (xx + len[i])) - (1ll << xx);
ret += __builtin_popcountll(mask & gr[yy]);
gr[yy] ^= mask;
}
return 2 * ret - len[i];
}
int add_rectangle(vector<LL>& gr, vector<Rec>& r, int i, int dir, int y,
int x) {
r[i] = {dir, y, x};
int ret = 0;
if (dir == 1) {
for (int j = 0; j < len[i]; ++j) {
ret += ((gr[y] >> x) & 1);
gr[y] ^= (1ll << x);
y++;
}
} else {
LL mask = (1ll << (x + len[i])) - (1ll << x);
ret += __builtin_popcountll(mask & gr[y]);
gr[y] ^= mask;
}
return 2 * ret - len[i];
}
void input() {
for (int i = 0; i < k; ++i) {
cin >> len[i];
}
int tmp = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
char tmp;
cin >> tmp;
grid[i] += ((LL)(tmp - '0') << j);
}
tmp += __builtin_popcountll(grid[i]);
}
DBG(tmp)
}
void output() {
for (int i = 0; i < k; ++i) {
if (ans[i].dir == 0) {
cout << ans[i].y + 1 << ' ' << ans[i].x + 1 << ' ' << ans[i].y + 1
<< ' ' << ans[i].x + len[i] << "\n";
} else {
cout << ans[i].y + 1 << ' ' << ans[i].x + 1 << ' ' << ans[i].y + len[i]
<< ' ' << ans[i].x + 1 << "\n";
}
}
}
void solve() {
input();
// randomize initial state
uniform_int_distribution<int> seed(0, 100);
int loop = seed(mt);
for (int i = 0; i < loop; ++i) {
xor128();
}
calc_SA();
output();
}
bool time_limit(double thres = 0.97 * 1) {
double t = chrono::duration_cast<chrono::milliseconds>(
chrono::system_clock::now() - start)
.count() /
1000.0;
#if MYDEBUG
thres *= 2.4;
#else
;
#endif
return t > thres;
}
double update_temperature() {
double t_left = (1000 - chrono::duration_cast<chrono::milliseconds>(
chrono::system_clock::now() - start)
.count());
#if MYDEBUG
t_left = (2400 - chrono::duration_cast<chrono::milliseconds>(
chrono::system_clock::now() - start)
.count()) /
2.4;
#else
;
#endif
t_left /= 1000;
// return 0.8 * pow(t_left, 0.8) * exp((t_left - 1) * 1);
return 0.8 * exp((t_left - 1) * 2.4) * pow(t_left, 1) *
((t_left * (1 - t_left) * (1 - t_left) * 4 + 1)) +
t_left * (1 - t_left) * (1 - t_left) * (1 - t_left) * 1.5;
// return t_left/2+0.02;
}
}; // namespace Problem
} // namespace Problem
int main() {
std::cin.tie(0);
std::ios_base::sync_with_stdio(false);
long long n = 0, k;
std::cin >> n >> k;
Problem::Solver sol(n, k);
sol.solve();
return 0;
}