結果

問題 No.5002 stick xor
コンテスト
ユーザー shamal_ref
提出日時 2018-05-26 23:34:13
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 1,000 ms
コード長 4,778 bytes
コンパイル時間 2,658 ms
実行使用メモリ 1,596 KB
スコア -139
最終ジャッジ日時 2018-05-26 23:34:17
ジャッジサーバー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 = numeric_limits<uint64_t>::max();

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

void solve(array<int, 500> L, array<uint64_t, 60> board) {
  Xorshift128 x128;
  array <Line, 500> ans;

  for (int i = 0; i < 500; i++) {
    ans[i].dir = i & 1;
    ans[i].l = L[i];
    ans[i].a = x128() % 60;
    ans[i].p = x128() % (61 - 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);
      x = x & (x << 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 == 0) ? -1 : 1;
        board[j] ^= x;
      }
    }
  }


  for (int i = 0; i < 500; i++) {
    if (ans[i].dir) {
      printf("%d %d %d %d\n", 60 - ans[i].p, ans[i].a + 1, 60 - (ans[i].p + ans[i].l - 1), ans[i].a + 1);
    }
    else {
      printf("%d %d %d %d\n", 60 - ans[i].a, ans[i].p + 1, 60 - ans[i].a, ans[i].p + ans[i].l);
    }
  }
  pv(score);
}

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