結果
| 問題 |
No.5002 stick xor
|
| コンテスト | |
| ユーザー |
 zenito9970
|
| 提出日時 | 2018-05-27 01:45:01 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 906 ms / 1,000 ms |
| コード長 | 6,491 bytes |
| コンパイル時間 | 33,717 ms |
| 実行使用メモリ | 1,624 KB |
| スコア | 23,897 |
| 最終ジャッジ日時 | 2018-05-27 01:48:03 |
|
ジャッジサーバーID （参考情報） |
judge6 / |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 |
ソースコード
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define repr(i,n) for(int i=(n)-1;0<=i;--i)
#define each(e,v) for(auto&& e:(v))
#define all(v) begin(v),end(v)
#define dump(x) cerr<<#x<<": "<<(x)<<endl
using namespace std;
using vint = vector<int>;
using ll = long long;
using vll = vector<ll>;
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }
#define imosPW(imos,x,y,l) do{\
(imos)[(y)][(x)]++; \
(imos)[(y)][(x)+(l)]--; \
(imos)[(y)+1][(x)]--; \
(imos)[(y)+1][(x)+(l)]++; } while(0);
#define imosMW(imos,x,y,l) do{\
(imos)[(y)][(x)]--; \
(imos)[(y)][(x)+(l)]++; \
(imos)[(y)+1][(x)]++; \
(imos)[(y)+1][(x)+(l)]--; } while(0);
#define imosPH(imos,x,y,l) do{\
(imos)[(y)][(x)]++; \
(imos)[(y)+(l)][(x)]--; \
(imos)[(y)][(x)+1]--; \
(imos)[(y)+(l)][(x)+1]++; } while(0);
#define imosMH(imos,x,y,l) do{\
(imos)[(y)][(x)]--; \
(imos)[(y)+(l)][(x)]++; \
(imos)[(y)][(x)+1]++; \
(imos)[(y)+(l)][(x)+1]--; } while(0);
namespace Timer {
using namespace std::chrono;
high_resolution_clock::time_point start_time;
inline void init() {
start_time = high_resolution_clock::now();
}
inline int now() {
auto now = high_resolution_clock::now();
auto t = now - start_time;
return duration_cast<milliseconds>(t).count();
}
inline bool check(int limit) {
return now() < limit;
}
}
struct Data {
bool isH;
int x, y;
};
void output(int l, Data d) {
int eX = d.isH ? d.x : (d.x + l - 1);
int eY = d.isH ? (d.y + l - 1) : d.y;
cout << d.y+1 << " " << d.x+1 << " " << eY+1 << " " << eX+1 << endl;
}
// vector<vint> imosX2grid(vector<vint> imos) {
// const int n = imos.size();
// rep(y, n) rep(x, n-1) {
// imos[y][x+1] += imos[y][x];
// }
// return imos;
// }
// int calcScore(const vector<vint>& grid) {
// const int n = grid.size();
// int cnt = 0;
// rep(y, n) rep(x, n) if(grid[y][x] % 2 == 0) cnt++;
// return cnt;
// }
int calcScore(const vector<vint>& A, vector<vint> imos) {
const int n = A.size();
rep(y, n) rep(x, n) imos[y][x+1] += imos[y][x];
rep(x, n) rep(y, n) imos[y+1][x] += imos[y][x];
int cnt = 0;
rep(y, n) rep(x, n) if((A[y][x] + imos[y][x]) % 2 == 0) cnt++;
return cnt;
}
int main() {
Timer::init();
int n, k; cin >> n >> k;
vint L(k);
rep(i, k) cin >> L[i];
vector<vint> A(n, vint(n));
rep(y, n) rep(x, n) { char c; cin >> c; A[y][x] = c == '1'; }
vector<vint> imos(n+1, vint(n+1, 0));
int initialScore = calcScore(A, imos);
dump(initialScore);
cerr << "random" << endl;
mt19937 mt(random_device{}());
vector<Data> data(k);
rep(i, k) {
data[i].isH = false;
int x = uniform_int_distribution<>(0, n - L[i])(mt);
int y = uniform_int_distribution<>(0, n-1)(mt);
data[i].x = x;
data[i].y = y;
imos[y][x]++;
imos[y][x + L[i]]--;
imos[y+1][x]--;
imos[y+1][x + L[i]]++;
}
int cycle = 0, cntAccept = 0;
int beforeScore = calcScore(A, imos);
vector<Data> bestData = data;
int bestScore = -1e9;
constexpr double paramA = 1;
constexpr double paramB = 4;
constexpr double initTemp = 100;
cerr << "while" << endl;
while(Timer::check(900)) {
cycle++;
// const double progress = (cycle + 0.5) / Num;
const double progress = Timer::now() / 900.0;
const double T = initTemp * pow(1 - progress, paramA) * exp2(-progress * paramB);
// nextStep
// int beforeScore = calcScore(A, imos);
// int rk = uniform_int_distribution<>(0, k-1)(mt);
int rk = cycle % k;
bool rotateMode = uniform_int_distribution<>(0, 1)(mt) == 0;
int rx, ry;
if(rotateMode) {
if(data[rk].isH) {
if(n <= data[rk].x + L[rk]) continue;
imosMH(imos, data[rk].x, data[rk].y, L[rk]);
imosPW(imos, data[rk].x, data[rk].y, L[rk]);
} else {
if(n <= data[rk].y + L[rk]) continue;
imosMW(imos, data[rk].x, data[rk].y, L[rk]);
imosPH(imos, data[rk].x, data[rk].y, L[rk]);
}
} else {
if(data[rk].isH) {
rx = uniform_int_distribution<>(0, n-1)(mt);
ry = uniform_int_distribution<>(0, n - L[rk])(mt);
imosMH(imos, data[rk].x, data[rk].y, L[rk]);
imosPH(imos, rx, ry, L[rk]);
} else {
rx = uniform_int_distribution<>(0, n - L[rk])(mt);
ry = uniform_int_distribution<>(0, n-1)(mt);
imosMW(imos, data[rk].x, data[rk].y, L[rk]);
imosPW(imos, rx, ry, L[rk]);
}
}
// imosMW(imos, data[rk].x, data[rk].y, L[rk]);
// imosPW(imos, rx, ry, L[rk]);
int newScore = calcScore(A, imos);
if(beforeScore < newScore) { // || uniform_real_distribution<>(0, 1)(mt) <= exp(newScore - beforeScore) / T) {
beforeScore = newScore;
if(rotateMode) {
data[rk].isH = !data[rk].isH;
} else {
data[rk].x = rx;
data[rk].y = ry;
}
cntAccept++;
if(bestScore < newScore) {
bestScore = newScore;
bestData = data;
}
} else {
if(rotateMode) {
if(data[rk].isH) {
imosMW(imos, data[rk].x, data[rk].y, L[rk]);
imosPH(imos, data[rk].x, data[rk].y, L[rk]);
} else {
imosMH(imos, data[rk].x, data[rk].y, L[rk]);
imosPW(imos, data[rk].x, data[rk].y, L[rk]);
}
} else {
if(data[rk].isH) {
imosMH(imos, data[rk].x, data[rk].y, L[rk]);
imosPH(imos, rx, ry, L[rk]);
} else {
imosMW(imos, data[rk].x, data[rk].y, L[rk]);
imosPW(imos, rx, ry, L[rk]);
}
}
}
}
cerr << "output" << endl;
rep(i, k) output(L[i], bestData[i]);
dump(cycle);
dump(cntAccept);
cerr << "score: " << (bestScore - initialScore) << endl;
return 0;
}