結果
問題 | No.5002 stick xor |
ユーザー | shamal_ref |
提出日時 | 2018-05-29 10:47:38 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 918 ms / 1,000 ms |
コード長 | 6,732 bytes |
コンパイル時間 | 30,460 ms |
実行使用メモリ | 1,740 KB |
スコア | 42,771 |
最終ジャッジ日時 | 2018-05-29 10:48:10 |
ジャッジサーバーID (参考情報) |
judge7 / |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 820 ms
1,732 KB |
testcase_01 | AC | 868 ms
1,740 KB |
testcase_02 | AC | 837 ms
1,740 KB |
testcase_03 | AC | 873 ms
1,732 KB |
testcase_04 | AC | 834 ms
1,736 KB |
testcase_05 | AC | 871 ms
1,736 KB |
testcase_06 | AC | 838 ms
1,736 KB |
testcase_07 | AC | 840 ms
1,736 KB |
testcase_08 | AC | 862 ms
1,732 KB |
testcase_09 | AC | 838 ms
1,736 KB |
testcase_10 | AC | 874 ms
1,736 KB |
testcase_11 | AC | 827 ms
1,736 KB |
testcase_12 | AC | 890 ms
1,736 KB |
testcase_13 | AC | 834 ms
1,736 KB |
testcase_14 | AC | 857 ms
1,732 KB |
testcase_15 | AC | 856 ms
1,732 KB |
testcase_16 | AC | 918 ms
1,736 KB |
testcase_17 | AC | 824 ms
1,736 KB |
testcase_18 | AC | 868 ms
1,732 KB |
testcase_19 | AC | 882 ms
1,732 KB |
testcase_20 | AC | 835 ms
1,736 KB |
testcase_21 | AC | 878 ms
1,736 KB |
testcase_22 | AC | 846 ms
1,732 KB |
testcase_23 | AC | 861 ms
1,732 KB |
testcase_24 | AC | 887 ms
1,732 KB |
testcase_25 | AC | 842 ms
1,736 KB |
testcase_26 | AC | 872 ms
1,736 KB |
testcase_27 | AC | 833 ms
1,736 KB |
testcase_28 | AC | 866 ms
1,736 KB |
testcase_29 | AC | 873 ms
1,732 KB |
testcase_30 | AC | 837 ms
1,732 KB |
testcase_31 | AC | 865 ms
1,732 KB |
ソースコード
// C++11 #include <algorithm> #include <array> #include <bitset> #include <chrono> #include <cmath> #include <iostream> #include <numeric> #include <random> #include <vector> #include <set> #include <unordered_set> 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 <class T> ostream& operator<<(ostream& os, vector<T> 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 <class T, size_t S> ostream& operator<<(ostream& os, array<T, S> 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 <class T> auto elapsed() const { return chrono::duration_cast<T>(clock::now() - startTime).count(); } public: Timer() { restart(); } void restart() { startTime = clock::now(); } auto milli() const { return elapsed<chrono::milliseconds>(); } auto micro() const { return elapsed<chrono::microseconds>(); } }; 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<result_type>::min(); } static constexpr result_type max() { return std::numeric_limits<result_type>::max(); } result_type operator()() { t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } }; template <typename T, typename Comp = std::less<T>> class PriorityQueue { public: using container = vector<T>; 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<uint64_t, 60> rotate(array<uint64_t, 60> const& board) { array<uint64_t, 60> 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<int, 500> L, array<uint64_t, 60> board) { Xorshift128 x128; array <Line, 500> 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<double> dist01(0.0, 1.0); int constexpr pWidth = 3; array<double, 2 * pWidth> 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<int, 500> L; array<uint64_t, 60> 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; }