結果
| 問題 | No.5002 stick xor |
| ユーザー |
 kimiyuki
|
| 提出日時 | 2018-05-26 02:53:38 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 986 ms / 1,000 ms |
| コード長 | 7,316 bytes |
| コンパイル時間 | 36,585 ms |
| 実行使用メモリ | 1,548 KB |
| スコア | 43,345 |
| 最終ジャッジ日時 | 2018-05-26 02:54:16 |
|
ジャッジサーバーID （参考情報） |
judge9 / |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 |
ソースコード
#pragma GCC optimize "O3"#pragma GCC target "avx2"#include <bits/stdc++.h>#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))#define REP3R(i, m, n) for (int i = int(n) - 1; (i) >= int(m); -- (i))#define ALL(x) begin(x), end(x)#define dump(x) cerr << #x " = " << x << endl#define unittest_name_helper(counter) unittest_ ## counter#define unittest_name(counter) unittest_name_helper(counter)#define unittest __attribute__((constructor)) void unittest_name(__COUNTER__) ()using ll = long long;using namespace std;template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;template <class T> inline void chmax(T & a, T const & b) { a = max(a, b); }template <class T> inline void chmin(T & a, T const & b) { a = min(a, b); }template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }template <typename T> ostream & operator << (ostream & out, vector<T> const & xs) { REP (i, int(xs.size()) - 1) out << xs[i] << ' '; if (not xs.empty()) out << xs.back(); return out; }constexpr int N = 60;constexpr int K = 500;constexpr int MAX_L = 25;constexpr int N2 = N * N;class xor_shift_128 {public:typedef uint32_t result_type;xor_shift_128(uint32_t seed = 42) {set_seed(seed);}void set_seed(uint32_t seed) {a = seed = 1812433253u * (seed ^ (seed >> 30));b = seed = 1812433253u * (seed ^ (seed >> 30)) + 1;c = seed = 1812433253u * (seed ^ (seed >> 30)) + 2;d = seed = 1812433253u * (seed ^ (seed >> 30)) + 3;}uint32_t operator() () {uint32_t t = (a ^ (a << 11));a = b; b = c; c = d;return d = (d ^ (d >> 19)) ^ (t ^ (t >> 8));}static constexpr uint32_t max() { return numeric_limits<result_type>::max(); }static constexpr uint32_t min() { return numeric_limits<result_type>::min(); }private:uint32_t a, b, c, d;};int count_black(int y, int x, bool is_vertical, int len, bitset<N2> const & a) {int cnt = 0;REP (i, len) {int ny = y + (is_vertical ? i : 0);int nx = x + (is_vertical ? 0 : i);cnt += a[ny * N + nx];}return cnt;}void apply_rect(int y, int x, bool is_vertical, int len, bitset<N2> & a) {REP (i, len) {int ny = y + (is_vertical ? i : 0);int nx = x + (is_vertical ? 0 : i);auto && p = a[ny * N + nx];p = not p;}}array<tuple<int, int, bool>, K> solve_greedy(array<int, K> const & l, bitset<N2> & a) {array<vector<int>, N + 1> lookup;REP (i, K) lookup[l[i]].push_back(i);array<tuple<int, int, bool>, K> result;REP_R (len, N + 1) {for (int i : lookup[len]) {int highscore = -1;REP (y, N) REP (x, N) REP (is_vertical, 2) {if ( is_vertical and y + len > N) continue;if (not is_vertical and x + len > N) continue;int score = count_black(y, x, is_vertical, l[i], a);if (highscore < score) {highscore = score;result[i] = make_tuple(y, x, is_vertical);}}assert (highscore != -1);int y, x; bool is_vertical; tie(y, x, is_vertical) = result[i];apply_rect(y, x, is_vertical, l[i], a);}}return result;}array<tuple<int, int, bool>, K> solve(array<int, K> const & l, bitset<N2> a) {const auto TLE = chrono::duration_cast<chrono::nanoseconds>(chrono::milliseconds(1000 - 20));chrono::high_resolution_clock::time_point clock_end = chrono::high_resolution_clock::now() + TLE;xor_shift_128 gen;array<tuple<int, int, bool>, K> result = solve_greedy(l, a);array<tuple<int, int, bool>, K> rects = result;int highscore = a.count();int score = highscore;int iteration = 0;double temperature = 1.0;for (; ; iteration ++) {if (iteration % 100 == 0) {temperature = (clock_end - chrono::high_resolution_clock::now()).count() / (double)TLE.count();if (temperature < 0) break;}int i = uniform_int_distribution<int>(0, K - 1)(gen);// prevint y1, x1; bool is_vertical1; tie(y1, x1, is_vertical1) = rects[i];apply_rect(y1, x1, is_vertical1, l[i], a);int black1 = count_black(y1, x1, is_vertical1, l[i], a);// nextbool is_vertical2 = bernoulli_distribution(0.5)(gen);int y2 = uniform_int_distribution<int>(0, (N - 1) - (is_vertical2 ? l[i] : 0))(gen);int x2 = uniform_int_distribution<int>(0, (N - 1) - (is_vertical2 ? 0 : l[i]))(gen);if (is_vertical2) {if (bernoulli_distribution(0.5)(gen)) {while (y2 - 1 >= 0 and (a[(y2 - 1) * N + x2] or not a[(y2 + l[i] - 1) * N + x1])) -- y2;} else {while (y2 + l[i] < N and (not a[y2 * N + x2] or a[(y2 + l[i]) * N + x2])) ++ y2;}} else {if (bernoulli_distribution(0.5)(gen)) {while (x2 - 1 >= 0 and (a[y2 * N + x2 - 1] or not a[y2 * N + x2 + l[i] - 1])) -- x2;} else {while (x2 + l[i] < N and (not a[y2 * N + x2] or a[y2 * N + x2 + l[i]])) ++ x2;}}int black2 = count_black(y2, x2, is_vertical2, l[i], a);double delta = black2 - black1;if (delta >= 0) { // or bernoulli_distribution(exp(delta / temperature))(gen)) {score -= l[i] - 2 * black1;assert (score == a.count());apply_rect(y2, x2, is_vertical2, l[i], a);score += l[i] - 2 * black2;assert (score == a.count());rects[i] = make_tuple(y2, x2, is_vertical2);if (score < highscore) {highscore = score;result = rects;cerr << "black = " << highscore << " / " << N2 << endl;}} else {apply_rect(y1, x1, is_vertical1, l[i], a);}}cerr << "iteration = " << iteration << endl;cerr << "black = " << highscore << " / " << N2 << endl;return result;}int main() {// input{ int n; cin >> n; assert (n == N); }{ int k; cin >> k; assert (k == K); }array<int, K> l;REP (i, K) cin >> l[i];bitset<N2> a;REP (y, N) REP (x, N) {char c; cin >> c;a[y * N + x] = c - '0';}// solvearray<tuple<int, int, bool>, K> result = solve(l, a);// outputint w0 = N2 - a.count();REP (i, K) {int y, x; bool is_vertical; tie(y, x, is_vertical) = result[i];int ny = y + (is_vertical ? l[i] - 1 : 0);int nx = x + (is_vertical ? 0 : l[i] - 1);cout << y + 1 << ' ' << x + 1 << ' ' << ny + 1 << ' ' << nx + 1 << endl;apply_rect(y, x, is_vertical, l[i], a);}cerr << "black = " << a.count() << " / " << N2 << endl;int wk = N2 - a.count();cerr << "raw score = " << wk - w0 << endl;return 0;}