#261326 (C++17) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: shamal_ref
• 提出日時: 2018-05-29 09:12:09
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 832 ms / 1,000 ms
• コード長: 6,732 bytes
• コンパイル時間: 28,407 ms
• 実行使用メモリ: 1,820 KB
• スコア: 42,245
• 最終ジャッジ日時: 2018-05-29 09:12:39
• ジャッジサーバーID （参考情報）: judge7 /

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	788 ms; 1,816 KB
testcase_01	AC	821 ms; 1,816 KB
testcase_02	AC	769 ms; 1,816 KB
testcase_03	AC	832 ms; 1,820 KB
testcase_04	AC	789 ms; 1,816 KB
testcase_05	AC	785 ms; 1,816 KB
testcase_06	AC	826 ms; 1,816 KB
testcase_07	AC	779 ms; 1,820 KB
testcase_08	AC	821 ms; 1,820 KB
testcase_09	AC	781 ms; 1,816 KB
testcase_10	AC	763 ms; 1,820 KB
testcase_11	AC	755 ms; 1,820 KB
testcase_12	AC	761 ms; 1,820 KB
testcase_13	AC	756 ms; 1,820 KB
testcase_14	AC	804 ms; 1,816 KB
testcase_15	AC	764 ms; 1,816 KB
testcase_16	AC	771 ms; 1,820 KB
testcase_17	AC	727 ms; 1,816 KB
testcase_18	AC	748 ms; 1,816 KB
testcase_19	AC	783 ms; 1,816 KB
testcase_20	AC	774 ms; 1,816 KB
testcase_21	AC	811 ms; 1,816 KB
testcase_22	AC	752 ms; 1,820 KB
testcase_23	AC	823 ms; 1,820 KB
testcase_24	AC	751 ms; 1,820 KB
testcase_25	AC	793 ms; 1,816 KB
testcase_26	AC	762 ms; 1,820 KB
testcase_27	AC	804 ms; 1,816 KB
testcase_28	AC	772 ms; 1,816 KB
testcase_29	AC	826 ms; 1,820 KB
testcase_30	AC	769 ms; 1,820 KB
testcase_31	AC	790 ms; 1,816 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_--;
  }
};



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

struct Line {
  int dir; //0: yoko, 1: tate
  int a;
  int p;
};

struct State {
  int turn = 0;
  int score;
  array<uint64_t, 60> board;
  array<Line, 500> ans;
};

struct Ope {
  State* parent;
  int score;
  Line line;
};

bool operator<(State const& a, State const& b) {
  return a.turn < b.turn;
}
bool operator<(Ope const& a, Ope const& b) {
  return a.score > b.score;
}


static constexpr int N = 500;
void solve(array<int, 500> L, array<uint64_t, 60> board) {
  auto const origBoard = board;

  State s0;
  s0.board = origBoard;

  int constexpr beamWidth = 25;
  PriorityQueue<Ope> opes0, opes1;
  opes0.setCapacity(beamWidth);
  opes1.setCapacity(beamWidth);

  Ope dummy;
  dummy.score = -10000;

  vector<State> states0, states1;
  states0.reserve(beamWidth);
  states1.reserve(beamWidth);
  states0.push_back(s0);

  for (int i = 0; i < 500; i++) {
    opes0.clear();
    while (opes0.size() < opes0.capacity()) opes0.push(dummy);

    for (auto& s : states0) {
      for (int yt = 0; yt < 2; yt++) {
        for (int a = 0; a < 60; a++) {
          for (int p = 0; p < (61 - L[i]); p++) {
            auto const b = ((uF >> (64 - L[i])) << p);
            int diff = 1000 * (2 * __builtin_popcountll(s.board[a] & b) - L[i]);
            //diff += 100 * ((s.board[a] & ((b << 1) ^ b)) == 0 ? 1 : 0);
            //diff += 100 * ((s.board[a] & ((b >> 1) ^ b)) == 0 ? 1 : 0);
            //int const nWhiteSide = 100 * (s.board[a] & l


            if (1000 * opes0.top().score < 1000 * s.score + diff) {
              opes0.pop();
              if (diff >= 0) opes0.push({ &s, s.score + diff / 1000, Line{yt, a, p} });
              else opes0.push({ &s, s.score + ((diff - 200) / 1000), Line{yt, a, p} });
            }
          }
        }
        s.board = rotate(s.board);
      }
    }

    states1.clear();
    for (auto ope : opes0) {
      states1.push_back(*(ope.parent));
      auto& ns = states1.back();

      ns.ans[i] = ope.line;
      ns.score = ope.score;
      if (ope.line.dir == 0) {
        ns.board[ope.line.a] ^= ((uF >> (64 - L[i])) << ope.line.p);
      }
      else {
        ns.board = rotate(ns.board);
        ns.board[ope.line.a] ^= ((uF >> (64 - L[i])) << ope.line.p);
        ns.board = rotate(ns.board);
      }
    }
    swap(states0, states1);
  }

  pv(globalTimer.milli());
  auto ans = max_element(states0.begin(), states0.end())->ans;
  auto score = max_element(states0.begin(), states0.end())->score;

  for (int i = 0; i < N; i++) {
    if (ans[i].dir == 0) {
      printf("%d %d %d %d\n", ans[i].a + 1, 61 - (ans[i].p + L[i]), 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 + L[i], 61 - (ans[i].a + 1));
    }
  }
  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;
}