結果

問題 No.5002 stick xor
ユーザー pirozhkipirozhki
提出日時 2018-05-29 12:52:57
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 891 ms / 1,000 ms
コード長 4,609 bytes
コンパイル時間 29,526 ms
実行使用メモリ 1,760 KB
スコア 27,273
最終ジャッジ日時 2018-05-29 12:53:28
ジャッジサーバーID
(参考情報)
judge6 /
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <type_traits>
using namespace std;
enum Dir {
UP,
DOWN,
RIGHT,
LEFT
};
struct Param {
int x;
int y;
int k;
Dir d;
};
void PrintParam(const Param& param) {
int x1 = param.x;
int y1 = param.y;
int x2 = param.x;
int y2 = param.y;
switch (param.d) {
case Dir::UP:
y1 -= param.k - 1;
break;
case Dir::DOWN:
y2 += param.k - 1;
break;
case Dir::RIGHT:
x2 += param.k - 1;
break;
case Dir::LEFT:
x1 -= param.k - 1;
break;
}
cout << y1 + 1 << " " << x1 + 1 << " " << y2 + 1 << " " << x2 + 1 << endl;
}
void PrintArray(const vector<bool>& arr, int n) {
for (unsigned int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
if ((i + 1) % n == 0) {
cout << endl;
}
}
cout << endl;
}
void Flip(vector<bool>& arr, int n, const Param& param) {
for (int i = 0; i < param.k; i++) {
switch (param.d) {
case Dir::UP:
arr[(param.y - i) * n + param.x].flip();
break;
case Dir::DOWN:
arr[(param.y + i) * n + param.x].flip();
break;
case Dir::RIGHT:
arr[param.y * n + (param.x + i)].flip();
break;
case Dir::LEFT:
arr[param.y * n + (param.x - i)].flip();
break;
}
}
}
int Evaluate(vector<bool> arr, int n, const vector<Param>& params, bool print = false) {
for (const Param& param : params) {
Flip(arr, n, param);
if (print) {
PrintArray(arr, n);
}
}
return count(arr.begin(), arr.end(), true);
}
bool IsValid(const Param& param, int n) {
switch (param.d) {
case Dir::UP:
if (param.y - (param.k - 1) < 0) {
return false;
}
break;
case Dir::DOWN:
if (param.y + (param.k - 1) > n - 1) {
return false;
}
break;
case Dir::RIGHT:
if (param.x + (param.k - 1) > n - 1) {
return false;
}
break;
case Dir::LEFT:
if (param.x - (param.k - 1) < 0) {
return false;
}
break;
}
return true;
}
void Read(vector<Param>& params, vector<bool>& arr, int& n) {
int k;
cin >> n >> k;
for (int i = 0; i < k; i++) {
Param p = { 0 };
cin >> p.k;
params.push_back(p);
}
string s;
for (int i = 0; i < n; i++) {
cin >> s;
for (char& c : s) {
if (c == '0') {
arr.push_back(0);
}
else {
arr.push_back(1);
}
}
}
}
template<class T>
class Random
{
public:
Random(T min, T max) : mt_(rd_()), dist_(min, max) {}
T operator()() {
return dist_(mt_);
}
private:
random_device rd_;
mt19937 mt_;
typename conditional<is_floating_point<T>::value, uniform_real_distribution<>, uniform_int_distribution<>>::type dist_;
};
double Probability(double e1, double e2, double t) {
if (e1 >= e2) {
return 1;
}
else {
return exp((e1 - e2) / t);
}
}
double Temperature(double r) {
double alpha = 0.5;
return pow(alpha, r);
}
class Randomize {
public:
Randomize(int n, int size) : rand_(0, size - 1), rand_pos_(0, n - 1), rand_dir_(0, 3), n_(n) {}
vector<Param> One(vector<Param>& params) {
int i = rand_();
do {
params[i].d = static_cast<Dir>(rand_dir_());
params[i].x = rand_pos_();
params[i].y = rand_pos_();
} while (!IsValid(params[i], n_));
return params;
}
vector<Param> All(vector<Param>& params) {
for (Param& param : params) {
do {
param.d = static_cast<Dir>(rand_dir_());
param.x = rand_pos_();
param.y = rand_pos_();
} while (!IsValid(param, n_));
}
return params;
}
private:
int n_;
Random<int> rand_;
Random<int> rand_pos_;
Random<int> rand_dir_;
};
//
vector<Param> Yakinamasi(const vector<Param>& params, const vector<bool>& arr, int n) {
vector<Param> current_params(params);
Randomize randomize(n, current_params.size());
randomize.All(current_params);
double current_e = Evaluate(arr, n, current_params);
vector<Param> best_params = current_params;
double best_e = current_e;
Random<double> rand(0, 1);
int goal_e = 0;
int itr_count = 35000;
for (int i = 0; i < itr_count; i++) {
vector<Param> next_params(current_params);
randomize.One(next_params);
double next_e = Evaluate(arr, n, next_params);
if (next_e < best_e) {
best_params = next_params;
best_e = next_e;
//cout << best_e << endl;
if (best_e <= goal_e) {
return best_params;
}
}
if (rand() <= Probability(current_e, next_e, Temperature(static_cast<double>(i) / itr_count))) {
current_params = next_params;
current_e = next_e;
}
}
return best_params;
}
int main() {
vector<Param> params;
vector<bool> arr;
int n;
Read(params, arr, n);
vector<Param> best_params = Yakinamasi(params, arr, n);
for (const Param& param : best_params) {
PrintParam(param);
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0