#911989 (C++17) No.2463 ストレートフラッシュ

提出ソース
結果

問題	No.2463 ストレートフラッシュ
コンテスト
ユーザー	tonegawa
提出日時	2023-09-08 22:15:25
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	67 ms / 2,000 ms
コード長	18,671 bytes
コンパイル時間	1,579 ms
コンパイル使用メモリ	148,540 KB
最終ジャッジ日時	2025-02-16 19:59:35
ジャッジサーバーID （参考情報）	judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 22
権限があれば一括ダウンロードができます
ソースコード

raw source code
#line 1 ".lib/template.hpp"


#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
  dest << p.first << ' ' << p.second;
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz;i++){
    int m = v[i].size();
    for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
  }
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << *itr;
    itr++;
    if(itr!=v.end()) dest << ' ';
  }
  return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << '(' << itr->first << ", " << itr->second << ')';
    itr++;
    if(itr!=v.end()) dest << '\n';
  }
  return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
  return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
  std::vector<T> v(sz);
  for(int i=0;i<(int)sz;i++) std::cin >> v[i];
  return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
  auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
  for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(tail...);
  return v;
}
void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

#line 1 ".lib/data_structure/bit_sequence/dynamic_bitset.hpp"


#line 1 ".lib/data_structure/bit_sequence/bit_operation.hpp"


#include <stdint.h>
#line 6 ".lib/data_structure/bit_sequence/bit_operation.hpp"
static constexpr __uint128_t mask_0_64 = ((__uint128_t)1 << 64) - 1;
//static constexpr uint64_t mask_32_64 = 0xFFFFFFFF00000000;
static constexpr uint64_t mask_0_32  = 0x00000000FFFFFFFF;
static constexpr uint64_t mask_48_64 = 0xFFFF000000000000;
static constexpr uint64_t mask_32_48 = 0x0000FFFF00000000;
static constexpr uint64_t mask_16_32 = 0x00000000FFFF0000;
static constexpr uint64_t mask_0_16  = 0x000000000000FFFF;
static constexpr int TABLE_SIZE_LOG = 16, TABLE_SIZE = 1 << TABLE_SIZE_LOG;

using __table =  std::vector<std::array<int8_t, TABLE_SIZE_LOG>>;
using __table_p =  std::vector<std::array<std::pair<int8_t, int8_t>, TABLE_SIZE_LOG>>;
__table select_build(){
  __table res(TABLE_SIZE);
  for(int i = 0; i < TABLE_SIZE; i++){
    res[i].fill(-1);
    int pcnt = 0;
    for(int j = 0; j < TABLE_SIZE_LOG; j++) if((i >> j) & 1) res[i][pcnt++] = j;
  }
  return res;
}
// k-bit目以降(kも含む)に初めて現れる1の位置, 無い場合は-1
int find_next_32bit(uint32_t x, int k){
  uint32_t b = x >> k;
  if(!b) return -1;
  return k + __builtin_ctz(b);
}
// k-bit目以降(kも含む)に初めて現れる1の位置, 無い場合は-1
int find_next_64bit(uint64_t x, int k){
  uint64_t b = x >> k;
  if(!b) return -1;
  return k + __builtin_ctzll(b);
}
// 0 <= k <= 63
// k-bit目以前(kも含む)に初めて現れる1の位置, 無い場合は-1
int find_prev_64bit(uint64_t x, int k){
  uint64_t b = x << (63 - k);
  if(!b) return -1;
  return k - __builtin_clzll(b);
}
// k番目(0-indexed)の1の場所(0-indexed)を返す. 無い場合壊れる
int select_32bit(uint32_t x, int k){
  static __table table = select_build();
  int r = __builtin_popcount(x & mask_0_16);
  if(r > k) return table[x & mask_0_16][k];
  return 16 + table[(x & mask_16_32) >> 16][k - r];
}
// k番目(0-indexed)の1の場所(0-indexed)を返す. 無い場合壊れる
int select_64bit(uint64_t x, int k){
  static __table table = select_build();
  int r = __builtin_popcount(x & mask_0_32);
  if(r > k){
    int rr = __builtin_popcount(x & mask_0_16);
    if(rr > k) return table[x & mask_0_16][k];
    else return 16 + table[(x & mask_16_32) >> 16][k - rr];
  }else{
    k -= r;
    int lr = __builtin_popcountll(x & mask_32_48);
    if(lr > k) return 32 + table[(x & mask_32_48) >> 32][k];
    else return 48 + table[(x & mask_48_64) >> 48][k - lr];
  }
}
// 先頭k_bit(0 <= k <= 32)の1の数
int rank_32bit(uint32_t x, int k){
  return k == 32 ? __builtin_popcount(x) : __builtin_popcount(x & ((1ULL << k) - 1));
}
// 先頭k_bit(0 <= k <= 64)の1の数
int rank_64bit(uint64_t x, int k){
  return k == 64 ? __builtin_popcountll(x) : __builtin_popcountll(x & ((1ULL << k) - 1));
}
// 128bit
int pop_count_128bit(__uint128_t x){
  return __builtin_popcountll(x >> 64) + __builtin_popcountll(x & mask_0_64);
}
int rank_128bit(__uint128_t x, int k){
  if(k == 128) return pop_count_128bit(x);
  if(k < 64) return __builtin_popcountll((x & mask_0_64) & ((1ULL << k) - 1));
  k -= 64;
  return __builtin_popcountll(x & mask_0_64) + __builtin_popcountll((x >> 64)  & ((1ULL << k) - 1));
}
// k番目の1, 無い場合壊れる
int select1_128bit(__uint128_t x, int k){
  int left_pop = __builtin_popcountll(x & mask_0_64);
  if(left_pop > k) return select_64bit(x & mask_0_64, k);
  return 64 + select_64bit(x >> 64, k - left_pop);
}
// k番目の0, 無い場合壊れる
int select0_128bit(__uint128_t x, int k){
  __uint128_t y = ~x;
  int left_unpop = __builtin_popcountll(y & mask_0_64);
  if(left_unpop > k) return select_64bit(y & mask_0_64, k);
  return 64 + select_64bit(y >> 64, k - left_unpop);
}
// k-bit目以降(kも含む)に初めて現れる1の位置, 無い場合は-1
int find_next_128bit(__uint128_t x, int k){
  __uint128_t b = x >> k;
  if(!b) return -1;
  // 末尾64bitが0
  if(!(b & mask_0_64)) return k + 64 + __builtin_ctzll(b >> 64);
  return k + __builtin_ctzll(b);
}
// 0 <= k <= 63
// k-bit目以前(kも含む)に初めて現れる1の位置, 無い場合は-1
int find_prev_128bit(__uint128_t x, int k){
  __uint128_t b = x << (127 - k);
  if(!b) return -1;
  // 先頭64bitが0
  if(!(b >> 64)) return k - 64 - __builtin_clzll(b);
  return k - __builtin_clzll(b >> 64);
}

#line 1 ".lib/data_structure/segment_tree/binary_indexed_tree.hpp"


#line 5 ".lib/data_structure/segment_tree/binary_indexed_tree.hpp"

template<typename Val = long long>
struct binary_indexed_tree{
  int M, H;
  std::vector<Val> sum;
  binary_indexed_tree(){}
  binary_indexed_tree(int N): M(N), H(31 - __builtin_clz(M)), sum(M + 1 , 0){}
  binary_indexed_tree(const std::vector<Val> &v): M(v.size()), H(31 - __builtin_clz(M)), sum(1){
    sum.insert(sum.begin() + 1, v.begin(), v.end());
    for(int i = 1; i <= v.size(); i++){
      int nxt = i + (i & (-i));
      if(nxt <= M) sum[nxt] += sum[i];
    }
  }
  void update(int k, Val x){
    for(int i = k + 1; i <= M; i += (i & (-i))) sum[i] += x;
  }
  Val query(int r){
    Val ret = 0;
    for(int k = r; k > 0; k -= (k & (-k))) ret += sum[k];
    return ret;
  }
  Val query(int l, int r){
    return query(r) - query(l);
  }
  // sum[0, k]がx以上になるような最小のkとsum[0, k], 無い場合は{M, 総和}
  // sumが単調非減少であることが必要
  using p = std::pair<int, Val>;
  p lower_bound(Val x){
    int v = 1 << H, h = H;
    Val s = 0, t = 0;
    while(h--){
      if(M < v) v -= 1 << h;
      else if(x <= s + sum[v]) t = s + sum[v], v -= 1 << h;
      else s += sum[v], v += 1 << h;
    }
    if(v == M + 1) return {M, s};
    return (x <= s + sum[v] ? p{v - 1, s + sum[v]} : p{v, t});
  }
};

#line 7 ".lib/data_structure/bit_sequence/dynamic_bitset.hpp"

// 同じサイズのbitset同士でしか演算できない
// サイズを変更する場合resize
// n, m, im: 最大サイズ, 最大ブロック, 内部的なサイズ(これ以降に1がないことが保証されている)
struct dynamic_bitset{
  static constexpr int BITLEN = 64, REM = 63, SHIFT = 6;
  int n, m, im;
  std::vector<uint64_t> v;

  uint64_t rightmost_mask(){
    return !(n & REM) ? ~0ULL : (1ULL << (n & REM)) - 1;
  }
  dynamic_bitset(): n(0), m(0), im(0){}
  dynamic_bitset(const dynamic_bitset &r): n(r.n), m(r.m), im(r.im), v(r.v.begin(), r.v.begin() + r.im){}
  dynamic_bitset(int n, bool f = 0): n(n), m((n + REM) >> SHIFT){
    if(f){
      im = m;
      v.resize(m, ~0ULL);
      v.back() &= rightmost_mask();
    }else im = 0;
  }
  // stringの左を0bit目とする
  dynamic_bitset(const std::string &s, char one = '1'): n(s.size()), m((n + REM) >> SHIFT), im(0){
    uint64_t sum = 0;
    for(int i = 0, j = 0, t = 0; i < n; i++){
      sum += (uint64_t)(s[i] == one) << j;
      if(i == n - 1 || j == REM){
        t++;
        v.push_back(sum);
        if(sum) im = t;
        sum = j = 0;
      }else j++;
    }
  }
  int size(){
    return n;
  }
  void set(int k, bool f){
    assert(0 <= k && k < n);
    int block = k >> SHIFT;
    if(f){
      if(block >= im) im = block + 1;
      while(block >= v.size()) v.resize(std::min((int)v.size() * 2 + 1, m), 0);
      v[block] |= (1ULL << (k & REM));
    }else if(block < im) v[block] &= ~(1ULL << (k & REM));
  }
  bool get(int k){
    return (k >> SHIFT) < im ? (v[k >> SHIFT] >> (k & REM)) & 1 : 0;
  }
  bool any(){
    for(int i = 0; i < im; i++) if(v[i]) return true;
    return false;
  }
  int find_first(){
    for(int i = 0; i < im; i++) if(v[i]) return i * BITLEN + find_next_64bit(v[i], 0);
    return -1;
  }
  bool all(){
    if(im != m) return false;
    for(int i = 0; i < m - 1; i++) if(v[i] != ~0ULL) return false;
    if(v[m - 1] != rightmost_mask()) return false;
    return true;
  }
  bool none(){
    return !any();
  }
  /*
  void resize(int s){
    m = (s + REM) >> SHIFT;
    if(m < im) v.resize(m), im = m;
    n = s;
    if(m == im) v[m - 1] &= rightmost_mask();
  }
  */
  dynamic_bitset operator ~(){
    dynamic_bitset res = *this;
    res.v.resize(m, ~0ULL);
    for(int i = 0; i < res.im; i++) res.v[i] = ~res.v[i];
    res.im = res.m;
    res.v[m - 1] &= res.rightmost_mask();
    return res;
  }
  dynamic_bitset operator ^ (const dynamic_bitset &r){
    dynamic_bitset res(*this);
    return res ^= r;
  }
  dynamic_bitset operator | (const dynamic_bitset &r){
    dynamic_bitset res(*this);
    return res |= r;
  }
  dynamic_bitset operator & (const dynamic_bitset &r){
    dynamic_bitset res(*this);
    return res &= r;
  }
  dynamic_bitset operator ^= (const dynamic_bitset &r){
    assert(n == r.n);
    if(im < r.im){
      im = r.im;
      v.resize(r.im, 0);
    }
    for(int i = 0; i < r.im; i++) v[i] ^= r.v[i];
    return *this;
  }
  dynamic_bitset operator |= (const dynamic_bitset &r){
    assert(n == r.n);
    if(im < r.im){
      im = r.im;
      v.resize(r.im, 0);
    }
    for(int i = 0; i < r.im; i++) v[i] |= r.v[i];
    return *this;
  }
  dynamic_bitset operator &= (const dynamic_bitset &r){
    assert(n == r.n);
    if(im > r.im){
      im = r.im;
      v.resize(im);
    }
    for(int i = 0; i < im; i++) v[i] &= r.v[i];
    return *this;
  }
  // 全てのビットが等しく, かつサイズも同じか
  bool operator == (const dynamic_bitset &r){
    if(n != r.n) return false;
    for(int i = 0; i < std::min(im, r.im); i++) if(v[i] != r.v[i]) return false;
    if(im > r.im){
      for(int i = r.im; i < im; i++) if(v[i]) return false;
    }else{
      for(int i = im; i < r.im; i++) if(r.v[i]) return false;
    }
    return true;
  }
  bool operator != (const dynamic_bitset &r){
    return !(*this == r);
  }
  // l |= r << s, l = rでもok
  static void lshift_or(dynamic_bitset &l, dynamic_bitset &r, int s){
    assert(l.n == r.n);
    int t = s & REM, k = s >> SHIFT;
    if(!t){
      int imr = std::min(r.m, r.im + k);
      l.im = std::max(l.im, imr);
      if(imr > l.v.size()) l.v.resize(imr, 0);
      for(int i = imr - 1; i >= k; i--) l.v[i] |= r.v[i - k];
      if(imr == l.m) l.v.back() &= l.rightmost_mask();
      return;
    }
    int imr = std::min(r.m, r.im + k + 1);
    l.im = std::max(l.im, imr);
    if(imr > l.v.size()) l.v.resize(imr, 0);
    int upper_bit = 64 - t;
    for(int i = imr - 1; i >= k; i--){
      if(i == k) l.v[i] |= r.v[i - k] << t;
      else l.v[i] |= (r.v[i - k] << t) | (r.v[i - k - 1] >> upper_bit);
    }
    if(imr == l.m) l.v.back() &= l.rightmost_mask();
  }
  // l ^= r << s, l = rでもok
  static void lshift_xor(dynamic_bitset &l, dynamic_bitset &r, int s){
    assert(l.n == r.n);
    int t = s & REM, k = s >> SHIFT;
    if(!t){
      int imr = std::min(r.m, r.im + k);
      l.im = std::max(l.im, imr);
      if(imr > l.v.size()) l.v.resize(imr, 0);
      for(int i = imr - 1; i >= k; i--) l.v[i] ^= r.v[i - k];
      if(imr == l.m) l.v.back() &= l.rightmost_mask();
      return;
    }
    int imr = std::min(r.m, r.im + k + 1);
    l.im = std::max(l.im, imr);
    if(imr > l.v.size()) l.v.resize(imr, 0);
    int upper_bit = 64 - t;
    for(int i = imr - 1; i >= k; i--){
      if(i == k) l.v[i] ^= r.v[i - k] << t;
      else l.v[i] ^= (r.v[i - k] << t) | (r.v[i - k - 1] >> upper_bit);
    }
    if(imr == l.m) l.v.back() &= l.rightmost_mask();
  }
  // l &= r << s, l = rでもok
  static void lshift_and(dynamic_bitset &l, dynamic_bitset &r, int s){
    assert(l.n == r.n);
    int t = s & REM, k = s >> SHIFT;
    if(!t){
      int imr = std::min(l.im, r.im + k);
      for(int i = imr - 1; i >= k; i--) l.v[i] &= r.v[i - k];
      for(int i = l.im - 1; i >= imr; i--) l.v[i] = 0;
      l.im = imr;
      return;
    }
    int imr = std::min(l.im, r.im + k + 1);
    int upper_bit = 64 - t;
    for(int i = imr - 1; i >= k; i--){
      if(i == k) l.v[i] &= r.v[i - k] << t;
      else l.v[i] &= (r.v[i - k] << t) | (r.v[i - k - 1] >> upper_bit);
    }
    for(int i = l.im - 1; i >= imr; i--) l.v[i] = 0;
    l.im = imr;
  }
  dynamic_bitset operator <<= (const int s){
    assert(0 <= s);
    int t = s & REM, k = s >> SHIFT;
    if(!t){
      im = std::min(m, im + k);
      if(im > v.size()) v.resize(im, 0);
      for(int i = im - 1; i >= 0; i--) v[i] = (i >= k ? v[i - k] : 0);
      if(im == m) v.back() &= rightmost_mask();
      return *this;
    }
    im = std::min(m, im + k + 1);
    if(im > v.size()) v.resize(im, 0);
    int upper_bit = 64 - t;
    for(int i = im - 1; i >= 0; i--){
      if(i < k) v[i] = 0;
      else if(i == k) v[i] = v[i - k] << t;
      else v[i] = (v[i - k] << t) | (v[i - k - 1] >> upper_bit);
    }
    if(im == m) v.back() &= rightmost_mask();
    return *this;
  }
  dynamic_bitset operator >>= (const int s){
    assert(0 <= s);
    int t = s & REM, k = s >> SHIFT;
    im -= k;
    if(!t){
      for(int i = 0; i < im; i++) v[i] = v[i + k];
      for(int i = std::max(0, im); i < im + k; i++) v[i] = 0;
      if(im < 0) im = 0;
      return *this;
    }
    int upper_bit = 64 - t;
    for(int i = 0; i < im; i++){
      if(i + k == (int)v.size() - 1) v[i] = v[i + k] >> t;
      else v[i] = (v[i + k] >> t) | (v[i + k + 1] << upper_bit);
    }
    for(int i = std::max(0, im); i < im + k; i++) v[i] = 0;
    if(im < 0) im = 0;
    return *this;
  }
  dynamic_bitset operator << (const int s){
    dynamic_bitset res(*this);
    return res <<= s;
  }
  dynamic_bitset operator >> (const int s){
    dynamic_bitset res(*this);
    return res >>= s;
  }
  int pop_count(){
    int res = 0;
    for(int i = 0; i < im; i++) res += __builtin_popcountll(v[i]);
    return res;
  }
};
std::ostream &operator<<(std::ostream &dest, const dynamic_bitset &v){
  if(!v.n) return dest;
  int cnt = 0;
  for(int i = 0; i < v.m; i++){
    if(i >= v.im){
      for(int j = 0; j < 64 && cnt < v.n; j++, cnt++) dest << 0;
    }else{
      for(int j = 0; j < 64 && cnt < v.n; j++, cnt++) dest << ((v.v[i] >> j) & 1);
    }
    if(i != v.m - 1) dest << ' ';
  }
  return dest;
}

#line 3 "a.cpp"

int main(){
  io_init();
  int n, m;
  std::cin >> n >> m;
  int ans = n * m;
  vector<pair<int, int>> x(n * m);
  range(i, 0, n * m){
    std::cin >> x[i].first >> x[i].second;
    x[i].first--, x[i].second--;
  }
  auto pos = make_vec<int>(m, n, -1);
  vector<vector<array<int, 5>>> pat(n);
  range(i, 0, n - 3){
    array<int, 5> y;
    range(j, 0, 5) y[j] = (i + j) % n;
    range(j, 0, 5) pat[y[j]].push_back(y);
  }
  /*
  range(i, 0, n){
    std::cout << "i " << i << '\n';
    range(j, 0, pat[i].size()){
      range(k, 0, 5){
        std::cout << pat[i][j][k] << ' ';
      }
      std::cout << '\n';
    }
  }
  */
  range(i, 0, n * m){
    auto [num, mk] = x[i];
    pos[mk][num] = i;
    range(j, 0, pat[num].size()){
      array<int, 5> y = pat[num][j];
      bool f = true;
      range(k, 0, 5){
        if(pos[mk][y[k]] == -1){
          f = false;
          break;
        }
        y[k] = pos[mk][y[k]];
      }
      if(!f) continue;
      sort(allof(y));
      int shu = 0, idx = 4, ok = 0;
      range(k, 0, 5) ok += y[k] < 5;
      while(ok < 5){
        int diff = y[ok] - idx; // 次のカードまでの位置
        int ng = 5 - ok;
        int tmp_shu = (diff + ng - 1) / ng;
        shu += tmp_shu;
        idx += tmp_shu * ng;
        while(ok < 5 && y[ok] <= idx) ok++;
      }
      ans = min(ans, shu);
    }
  }
  std::cout << ans << '\n';
}
yukicoder

結果

ソースコード
