// C++11 #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define pv(val) cerr << #val << '=' << (val) << endl #define pvn(name, val) cerr << name << '=' << (val) << endl #define pl cerr << '@' << __LINE__ << endl static constexpr uint64_t u0 = 0ull; static constexpr uint64_t u1 = 1ull; static constexpr uint64_t uF = 0xFFFFFFFFFFFFFFFFull; #ifdef _MSC_VER //dummy int __builtin_popcountll(unsigned long long) { return 0; } int __builtin_clzll(unsigned long long) { return 0; } #endif template ostream& operator<<(ostream& os, vector const& vec) { if (vec.empty()) { os << "{}"; } else { os << '{'; for (size_t i = 0; i < vec.size() - 1; i++) os << vec[i] << ", "; os << vec.back() << '}'; } return os; } template ostream& operator<<(ostream& os, array const& arr) { if (arr.empty()) { os << "{}"; } else { os << '{'; for (size_t i = 0; i < arr.size() - 1; i++) os << arr[i] << ", "; os << arr.back() << '}'; } return os; } class Timer { using clock = chrono::high_resolution_clock; clock::time_point startTime; template auto elapsed() const { return chrono::duration_cast(clock::now() - startTime).count(); } public: Timer() { restart(); } void restart() { startTime = clock::now(); } auto milli() const { return elapsed(); } auto micro() const { return elapsed(); } }; Timer globalTimer; class Xorshift128 { uint32_t x, y, z, w, t; public: using result_type = uint32_t; Xorshift128(uint32_t seed = 12433) : x(123456789), y(362436069), z(521288629), w(seed) {} static constexpr result_type min() { return std::numeric_limits::min(); } static constexpr result_type max() { return std::numeric_limits::max(); } result_type operator()() { t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } }; template > class PriorityQueue { public: using container = vector; using iterator = typename container::iterator; using const_iterator = typename container::const_iterator; private: container queue_; size_t last_; public: PriorityQueue() { last_ = 0; } size_t size() const { return last_; } const_iterator begin() const { return queue_.begin(); } const_iterator end() const { return queue_.begin() + last_; } bool full() const { return size() == capacity(); } void setCapacity(size_t n) { queue_.resize(n); } size_t capacity() const { return queue_.size(); } void push(const T& val) { queue_[last_] = val; last_++; std::push_heap(queue_.begin(), queue_.begin() + last_, Comp()); } void push(T&& val) { queue_[last_] = std::move(val); last_++; std::push_heap(queue_.begin(), queue_.begin() + last_, Comp()); } void clear() { last_ = 0; } T const& top() const { return queue_[0]; } void pop() { std::pop_heap(queue_.begin(), queue_.begin() + last_, Comp()); last_--; } }; struct Line { bool dir; //true: yoko, false: tate int l; int a; int p; uint64_t b; }; array rotate(array const& board) { array result; for (int y = 0; y < 60; y++) { result[y] = 0; for (int x = 0; x < 60; x++) { result[y] |= (board[x] & (u1 << y)) == 0 ? u0 : (u1 << x); } } return result; } void solve(array L, array board) { Xorshift128 x128; array ans; int constexpr div = 250; for (int i = 0; i < 500; i++) { ans[i].dir = (i < div); ans[i].l = L[i]; ans[i].a = i % 60; ans[i].p = x128() % (61 - ans[i].l); ans[i].b = uF >> (64 - ans[i].l); } int score = 0; for (int i = 0; i < 500; i++) { if (ans[i].dir) { score += __builtin_popcountll(board[ans[i].a]); auto x = (uF >> (64 - ans[i].l)) << ans[i].p; board[ans[i].a] ^= x; score -= __builtin_popcountll(board[ans[i].a]); } else { auto x = u1 << ans[i].a; for (int j = ans[i].p; j < ans[i].p + ans[i].l; j++) { score += ((board[j] & x) == u0) ? -1 : 1; board[j] ^= x; } } } uniform_real_distribution dist01(0.0, 1.0); int constexpr pWidth = 3; array expTable; for (int i = 0; i < expTable.size(); i++) { expTable[i] = exp(-2.0 * pWidth + i); } double constexpr s01 = 1.0 / x128.max(); uint64_t nIters = 0, nAc = 0; int bestScore = 0; for (double t = 1.0; t > 0.00001; t *= 0.9995) { for (int yt = 0; yt < 2; yt++) { for (int i = yt * div; i < (yt == 0 ? div : 500); i++) { int nextP = (ans[i].p + x128() % (2 * pWidth + 1) - pWidth); int nextA = (ans[i].a + (x128() % 3 - 1) + 60) % 60; nextP = x128() % (61 - ans[i].l); nextA = x128() % 60; if (nextP < 0 || nextP + ans[i].l > 60) continue; auto const prevB = ans[i].b << ans[i].p; int const prevDiff = -(2 * __builtin_popcountll(board[ans[i].a] & prevB) - ans[i].l); board[ans[i].a] ^= prevB; //外す auto const nextB = (ans[i].b << nextP); int const diff = 2 * __builtin_popcountll(board[nextA] & nextB) - ans[i].l; ++nIters; if (diff >= prevDiff || exp((diff - prevDiff) / t) > s01 * x128()) { ++nAc; board[nextA] ^= nextB; ans[i].p = nextP; ans[i].a = nextA; score += -prevDiff + diff; if (score > bestScore) { bestScore = score; } } else { board[ans[i].a] ^= prevB; //戻す } } board = rotate(board); } } pv(nAc); pv(nIters); pvn("ratio", (double)nAc / nIters); for (int i = 0; i < 500; i++) { if (ans[i].dir) { printf("%d %d %d %d\n", ans[i].a + 1, 61 - (ans[i].p + ans[i].l), ans[i].a + 1, 61 - (ans[i].p + 1)); } else { printf("%d %d %d %d\n", ans[i].p + 1, 61 - (ans[i].a + 1), ans[i].p + ans[i].l, 61 - (ans[i].a + 1)); } } pv(nIters); pvn("Score", score); pvn("Time", globalTimer.milli()); } int main(void) { cin.tie(0); ios::sync_with_stdio(false); int N, K; array L; array board; cin >> N >> K; for (int i = 0; i < 500; i++) { cin >> L[i]; } string line; for (int i = 0; i < 60; i++) { cin >> line; std::bitset<64> bs(line); board[i] = bs.to_ullong(); } solve(L, board); return 0; }