結果

問題 No.5002 stick xor
ユーザー hakomohakomo
提出日時 2018-05-26 13:29:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 955 ms / 1,000 ms
コード長 5,915 bytes
コンパイル時間 33,702 ms
実行使用メモリ 2,380 KB
スコア 46,323
最終ジャッジ日時 2018-05-26 13:29:56
ジャッジサーバーID
(参考情報)
judge6 /
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <iostream>
#include <random>
#include <vector>
using namespace std;
#define U(v) cerr << #v << ": " << (v) << endl
class timer {
vector<timer> timers;
int n = 0;
public:
double limit = 0.95;
double t = 0;
timer() {}
timer(int size) : timers(size) {}
bool elapses() const {
return time() - t > limit;
}
void measure() {
t = time() - t;
++n;
}
void measure(char id) {
timers[id].measure();
}
void print() {
if (n % 2)
measure();
for (int i = 0; i < 128; ++i) {
if (timers[i].n)
cerr << (char)i << ' ' << timers[i].t << 's' << endl;
}
cerr << " " << t << 's' << endl;
}
static double time() {
#ifdef LOCAL
return __rdtsc() / 3.3e9;
#else
return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count() / 1000.0;
#endif
}
} timer(128);
class {
//unsigned y = 2463534242;
unsigned y = random_device()();
public:
unsigned next() {
return y ^= (y ^= (y ^= y << 13) >> 17) << 5;
}
int next(int b) {
return next() % b;
}
int next(int a, int b) {
return next(b - a) + a;
}
double nextDouble(double b = 1) {
return b * next() / 4294967296.0;
}
double nextDouble(double a, double b) {
return nextDouble(b - a) + a;
}
int operator() (int b) {
return next(b);
}
} rando;
constexpr int N = 60;
constexpr int K = 500;
int L[K];
bool A[N][N];
vector<array<int, 5>> states, bestStates;
int score, bestScore;
double ths[128];
inline void flip(const array<int, 5>& r) {
if (r[2] != 1) {
for (int x = r[0]; x < r[0] + r[2]; ++x)
A[r[1]][x] ^= 1;
} else {
for (int y = r[1]; y < r[1] + r[3]; ++y)
A[y][r[0]] ^= 1;
}
}
int main(int argc, char** argv) {
timer.measure();
{
int k;
cin >> k >> k;
for (int i = 0; i < K; ++i)
cin >> L[i];
char s[61];
for (int y = 0; y < N; ++y) {
cin >> s;
for (int x = 0; x < N; ++x)
A[y][x] = s[x] == '1';
}
}
//{
// mt19937 mt(atoi(argv[1]));
// for (int i = 0; i < K; ++i)
// L[i] = mt() % 25 + 1;
// for (int y = 0; y < N; ++y)
// for (int x = 0; x < N; ++x)
// A[y][x] = mt() % 2 == 1;
//}
for (int i = 0; i < K; ++i) {
int x = rando.next(N - L[i] + 1);
int y = rando.next(N);
if (rando.next(2)) {
states.emplace_back(array<int, 5>{ x, y, L[i], 1, i });
} else {
states.emplace_back(array<int, 5>{ y, x, 1, L[i], i });
}
flip(states.back());
}
score = bestScore = 0;
bestStates = states;
int ni = -1;
vector<array<int, 3>> ne;
for (int i = 0; i < K; ++i)
for (int j = 0; j < 2; ++j)
for (int k = 0; k < N; ++k)
ne.emplace_back(array<int, 3>{ i, j, k });
random_shuffle(ne.begin(), ne.end(), rando);
for (int iter = -1; ; ) {
if ((++iter & 0xfff) == 0) {
double p = 1 - (timer.time() - timer.t) / timer.limit;
if (p < 0) {
//U(iter);
break;
}
constexpr double InitialHeat = 0.8;
constexpr double FinalHeat = 1e-9;
double heat = p * (InitialHeat - FinalHeat) + FinalHeat;
for (int i = 0; i < 128; ++i)
ths[i] = log((i + 0.5) / 128) * heat;
random_shuffle(ths, ths + 128, rando);
}
if (++ni == ne.size()) ni = 0;
auto& r = states[ne[ni][0]];
int l, diff = 0;
if (r[2] != 1) {
l = r[2];
for (int x = r[0]; x < r[0] + r[2]; ++x)
diff += (A[r[1]][x] ^= 1) ? -1 : 1;
} else {
l = r[3];
for (int y = r[1]; y < r[1] + r[3]; ++y)
diff += (A[y][r[0]] ^= 1) ? -1 : 1;
}
int th = (int)floor((ths[iter & 127] - diff + l) / 2);
static vector<array<int, 5>> candidates;
candidates.clear();
if (ne[ni][1]) {
int y = ne[ni][2];
int b = 0;
for (int x = 0; x < l; ++x)
b += A[y][x];
for (int x = 0; ; ++x) {
if (b > th)
candidates.emplace_back(array<int, 5>{ x, y, l, 1, b * 2 - l + diff });
if (x + l == N) break;
b -= A[y][x] - A[y][x + l];
}
} else {
int x = ne[ni][2];
int b = 0;
for (int y = 0; y < l; ++y)
b += A[y][x];
for (int y = 0; ; ++y) {
if (b > th)
candidates.emplace_back(array<int, 5>{ x, y, 1, l, b * 2 - l + diff });
if (y + l == N) break;
b -= A[y][x] - A[y + l][x];
}
}
if (candidates.empty()) {
flip(r);
continue;
}
auto& c = candidates.size() == 1 ? candidates[0] : candidates[rando.next((int)candidates.size())];
score += c[4];
r[0] = c[0];
r[1] = c[1];
r[2] = c[2];
r[3] = c[3];
flip(r);
if (bestScore < score) {
bestScore = score;
bestStates = states;
}
}
score = bestScore;
states.swap(bestStates);
sort(states.begin(), states.end(), [](const array<int, 5>& a, const array<int, 5>& b) {
return a[4] < b[4];
});
for (auto& r : states)
cout << r[1] + 1 << ' ' << r[0] + 1 << ' ' << r[1] + r[3] << ' ' << r[0] + r[2] << endl;
//cout << "# " << atoi(argv[1]) << ',' << score << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0