結果

問題 No.5002 stick xor
コンテスト
ユーザー shamal_ref
提出日時 2018-05-29 10:47:38
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.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 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 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;
}
0