結果

問題 No.5002 stick xor
コンテスト
ユーザー shamal_ref
提出日時 2018-05-26 14:12:42
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,581 bytes
コンパイル時間 2,153 ms
実行使用メモリ 1,532 KB
スコア 0
最終ジャッジ日時 2018-05-26 14:12:46
ジャッジサーバーID
（参考情報） 		judge10 /
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 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 {
  int a;
  int b, c;
};

void solve(array<int, 500> L, array<uint64_t, 60> board) {
  Xorshift128 x128;
  std::uniform_int_distribution<int> dist59(0, 60);
  std::uniform_int_distribution<int> dist60(0, 60);
  std::uniform_int_distribution<int> dist249(0, 249);

  array<Line, 250> ansYoko, ansTate;
  for (int i = 0; i < 250; i++) {
   ansYoko[i].a = dist59(x128);
   ansYoko[i].b = dist60(x128);
   ansYoko[i].c = dist60(x128);
   if (ansYoko[i].b > ansYoko[i].c) swap(ansYoko[i].b, ansYoko[i].c);
   
   ansTate[i].a = dist59(x128);
   ansTate[i].b = dist60(x128);
   ansTate[i].c = dist60(x128);
   if (ansTate[i].b > ansTate[i].c) swap(ansTate[i].b, ansTate[i].c);
  }

  int score = 0;
  for (int i = 0; i < 250; i++) {
    auto yoko = ansYoko[i];
    int diffW = __builtin_popcountll(board[yoko.a]);
    auto x = uF << yoko.b;
    x = x >> (64 - yoko.c) & x;
    board[yoko.a] = x;
    diffW = __builtin_popcountll(board[yoko.a]) - diffW;

    auto tate = ansTate[i];
    x = u1 << tate.a;
    for (int j = tate.b; j < tate.c; j++) {
      diffW += (board[tate.a] & x == 0) ? -1 : 1;
      board[tate.a] ^= x;
    }
    score += diffW;
  }

  int rem = 0;
  for (int i = 0; i < 250; i++) {
    auto yoko = ansYoko[i];
    if (yoko.b == yoko.c) {
      rem++;
    }
    else {
      cout << (60 - yoko.b) << ' ' << (yoko.a + 1) << ' ' << (60 - yoko.c) << ' ' << (yoko.a + 1) << endl;
    }

    auto tate = ansTate[i];
    if (tate.b == tate.c) {
      rem++;
    }
    else {
      cout << (60 - tate.a) << ' ' << (tate.b + 1) << ' ' << (60 - tate.a) << ' ' << (tate.c + 1) << endl;
    }
  }

  while (rem > 0) {
    for (int i = 0; i < 60; i++) {
      while (board[i] != 0) {
        int j = 63 - __builtin_clzll(board[i]);
        auto x = ~(u1 << j);
        board[i] &= x;
        cout << (60 - j) << ' ' << i << ' ' << (60 - j) << ' ' << i << endl;
        ++score;
        --rem;
        if (rem == 0) goto END;
      }
    }
  }
END:;
  pv(score);
}

int main(void)
{
  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