#643392 (C++17) No.1463 Hungry Kanten

提出ソース

結果

問題	No.1463 Hungry Kanten
ユーザー	👑 Nachia
提出日時	2021-04-02 22:35:33
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	638 ms / 2,000 ms
コード長	13,410 bytes
コンパイル時間	2,644 ms
コンパイル使用メモリ	216,096 KB
実行使用メモリ	32,512 KB
最終ジャッジ日時	2024-06-06 09:25:43
合計ジャッジ時間	5,471 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	22 ms 5,376 KB
testcase_03	AC	461 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	638 ms 32,512 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	3 ms 5,376 KB
testcase_12	AC	4 ms 5,376 KB
testcase_13	AC	3 ms 5,376 KB
testcase_14	AC	8 ms 5,376 KB
testcase_15	AC	3 ms 5,376 KB
testcase_16	AC	24 ms 5,376 KB
testcase_17	AC	69 ms 6,944 KB
testcase_18	AC	23 ms 5,376 KB
testcase_19	AC	329 ms 18,304 KB
testcase_20	AC	468 ms 21,120 KB
testcase_21	AC	3 ms 5,376 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function 'basic_fixed_decimal::my_type& basic_fixed_decimal::operator/=(const my_type&)':
main.cpp:308:50: warning: 'void* __builtin_memmove(void*, const void*, long unsigned int)' writing 64 bytes into a region of size 56 overflows the destination [-Wstringop-overflow=]
  308 |       for(int j=array_size-1; j>=0; j--) buf[j+1]=buf[j];
main.cpp:302:17: note: at offset 8 into destination object 'buf' of size 64
  302 |     number_type buf; buf.fill(0);
      |                 ^~~

ソースコード

raw source code

#include<array>
#include<string>
#include<iostream>
#include<sstream>
#include<iomanip>
#include<algorithm>
#include<assert.h>
#include<math.h>


template<class data_type, class idx_type, data_type g, idx_type max_idx>
class base_power_class{
public:
  data_type data[max_idx+1];
  constexpr base_power_class() : data() {
    data[0]=1;
    for(idx_type i=0; i<max_idx; i++) data[i+1]=data[i]*g;
  }
  constexpr data_type operator[](int idx) const { return data[idx]; }
};


class basic_fixed_decimal{
public:
  using digit_type = unsigned long long;
  using index_type = int;
  using sign_type = bool;
  using my_type = basic_fixed_decimal;
  static constexpr digit_type min_base = 10;
  static constexpr int base_size = 8;
  static constexpr auto base_power = base_power_class<digit_type,index_type,min_base,base_size>();
  static constexpr digit_type base = base_power[base_size];
  static constexpr index_type decimal_size = 0;
  static constexpr index_type integer_size = 8;
  static constexpr sign_type sign_pos = false;
  static constexpr sign_type sign_neg = true;
  static constexpr int array_size = decimal_size + integer_size;
  using number_type = std::array<digit_type,array_size>;
  static const my_type PI;
  static const my_type NAPIER;
  number_type D;
  sign_type sign;
  // O(N) (N=precision)
  basic_fixed_decimal(){
    D.fill(0);
    sign=sign_pos;
  }
  // O(N) (N=precision)
  basic_fixed_decimal(const std::string& S){
    D.fill(0);
    sign=sign_pos;
    assert(S.size()!=0);
    std::size_t beginpos=0;
    if(S[0]=='-'){ beginpos++; sign=sign_neg; }
    std::size_t pointpos=S.find('.',beginpos);
    if(pointpos==std::string::npos) pointpos=S.size();
    assert(beginpos<pointpos);
    assert(integer_size*base_size>=pointpos-beginpos); // 整数部の桁数を超過
    for(int i=beginpos; i<pointpos; i++){
      assert('0'<=S[i] && S[i]<='9');
      digit_type d = S[i]-'0';
      index_type digit_idx = decimal_size*base_size+(pointpos-1-i);
      D[digit_idx/base_size] += d * base_power[digit_idx%base_size];
    }
    if(pointpos!=S.size()) assert(pointpos+1<S.size());
    for(int i=pointpos+1; i<S.size(); i++){
      assert('0'<=S[i] && S[i]<='9');
      if(i-pointpos>decimal_size*base_size) continue; // 精度の外をカット
      digit_type d = S[i]-'0';
      index_type digit_idx = decimal_size*base_size+(pointpos-i);
      D[digit_idx/base_size] += d * base_power[digit_idx%base_size];
    }
  }
  // O(N) (N=precision)
  basic_fixed_decimal(double val){
    assert(val<2.0*std::pow((double)base,integer_size));
    std::string buf;
    std::ostringstream sstr(buf);
    sstr<<std::fixed<<std::setprecision(decimal_size)<<val<<std::flush;
    *this = my_type(sstr.str());
  }
  // O(1)
  digit_type operator[](index_type idx) const {
    assert(-decimal_size*base_size <= idx && idx < integer_size*base_size);
    idx += decimal_size*base_size;
    return D[idx/base_size]/base_power[idx%base_size]%min_base;
  }
  // O(N) (N=precision)
  std::string to_string() const {
    std::string buf; buf.reserve(array_size*base_size+4);
    bool decimal_hit=false;
    for(int i=-decimal_size*base_size; i<0; i++){
      if(decimal_hit){ buf.push_back(char(operator[](i)+'0')); }
      else if(operator[](i)!=0){ decimal_hit=true; buf.push_back(char(operator[](i)+'0')); }
    }
    if(decimal_hit) buf.push_back('.');
    auto integer_hit=buf.size();
    for(int i=0; i<integer_size*base_size; i++){
      buf.push_back(char(operator[](i)+'0'));
      if(operator[](i)!=0) integer_hit=buf.size();
    }
    buf.resize(integer_hit);
    if(sign==sign_neg) if(!is_zero()) buf.push_back('-');
    std::reverse(buf.begin(),buf.end());
    return std::string(buf);
  }
  // O(N) (N=precision)
  static bool cmp_unsigned(const number_type& l,const number_type& r){
    for(index_type i=array_size-1; i>=0; i--){
      if(l[i]!=r[i]) return l[i]<r[i];
    }
    return false;
  }
  // O(N) (N=precision)
  static bool add_unsigned(number_type& dst,const number_type& l,const number_type& r){
    digit_type overflow=0;
    for(index_type i=0; i<array_size; i++){
      digit_type d = l[i]+r[i]+overflow;
      overflow=0;
      if(d>=base){ overflow=1; d-=base; }
      dst[i]=d;
    }
    return overflow!=0;
  }
  // O(N) (N=precision)
  static bool subtract_unsigned(number_type& dst,const number_type& l,const number_type& r){
    digit_type underflow=0;
    for(index_type i=0; i<array_size; i++){
      digit_type d = l[i]+base-r[i]-underflow;
      underflow=1;
      if(d>=base){ underflow=0; d-=base; }
      dst[i]=d;
    }
    return underflow!=0;
  }
  // O(N^2) (N=precision)
  static sign_type multiply_sign(sign_type l,sign_type r){
    return (l || r) && !(l && r); // l xor r
  }
  // O(N) (N=precision)
  static bool add_lsb_unsigned(number_type& dst){
    for(int i=0; i<array_size; i++){
      dst[i]++;
      if(dst[i]<base) return false;
      dst[i]=0;
    }
    return true;
  }
  // O(N) (N=precision)
  static bool half_unsigned(number_type& dst){
    bool res = dst[0]%2==1;
    dst[0]/=2;
    for(int i=1; i<array_size; i++){
      if(dst[i]%2==1) dst[i-1]+=base/2;
      dst[i]/=2;
    }
    return res;
  }
  // O(N) (N=precision)
  static digit_type digit_multyply_unsigned(number_type& dst,const number_type& l,digit_type r){
    digit_type overflow = 0;
    for(int i=0; i<array_size; i++){
      overflow+=l[i]*r;
      dst[i]=overflow%base;
      overflow/=base;
    }
    return overflow;
  }
  // O(1)
  void set_digit(index_type idx,digit_type digit){
    assert(0 <= digit && digit < min_base);
    idx += decimal_size*base_size;
    auto& tg = D[idx/base_size];
    auto d = base_power[idx%base_size];
    tg = (tg/d/min_base*min_base+digit)*d;
  }
  // O(1)
  digit_type get_digit(index_type idx){
    return operator[](idx);
  }
  // O(N) (N=precision)
  my_type operator-() const {
    my_type buf = *this;
    buf.sign = !buf.sign;
    return buf;
  }
  // O(N) (N=precision)
  my_type& operator+=(const my_type& r){
    my_type buf;
    if(sign == r.sign){
      bool overflow = add_unsigned(buf.D,D,r.D);
      buf.sign=sign;
      assert(!overflow);
    }
    else{
      if(cmp_unsigned(D,r.D)){
        bool underflow = subtract_unsigned(buf.D,r.D,D);
        buf.sign=r.sign;
        assert(!underflow);
      }
      else{
        bool underflow = subtract_unsigned(buf.D,D,r.D);
        buf.sign=sign;
        assert(!underflow);
      }
    }
    *this=buf;
    return *this;
  }
  // O(N) (N=precision)
  my_type& operator-=(const my_type& r){
    return operator+=(-r);
  }
  // O(N^2) (N=precision)
  my_type& operator*=(const my_type& r){
    std::array<digit_type,array_size*2> buf; buf.fill(0);
    for(int i=0; i<array_size; i++){
      digit_type overflow = 0;
      for(int j=0; j<array_size; j++){
        overflow += D[i] * r.D[j] + buf[i+j];
        buf[i+j] = overflow % base;
        overflow /= base;
      }
      buf[i+array_size] = overflow;
    }
    for(int i=decimal_size*2+integer_size; i<array_size*2; i++){
      assert(buf[i]==0);
    }
    sign = multiply_sign(sign,r.sign);
    for(int i=0; i<array_size; i++) D[i]=buf[decimal_size+i];
    if(buf[decimal_size-1]>=base/2) assert(!add_lsb_unsigned(D));
    return *this;
  }
  // O(N) (N=precision)
  my_type operator+(const my_type& r) const {
    my_type buf=*this; buf+=r; return buf;
  }
  // O(N) (N=precision)
  my_type operator-(const my_type& r) const {
    my_type buf=*this; buf-=r; return buf;
  }
  // O(N^2) (N=precision)
  my_type operator*(const my_type& r) const {
    my_type buf=*this; buf*=r; return buf;
  }
  // O(N^2) (N=precision)
  my_type operator/(const my_type& r) const {
    my_type buf=*this; buf/=r; return buf;
  }
  // O(N) (N=precision)
  bool operator<(const my_type& r) const {
    if(sign==sign_pos && r.sign==sign_neg) return false;
    if(sign==sign_neg && r.sign==sign_pos) return true;
    if(sign==sign_pos) return cmp_unsigned(D,r.D);
    return cmp_unsigned(r.D,D);
  }
  // O(N) (N=precision)
  bool operator>(const my_type& r) const {
    return r < *this;
  }
  // O(N) (N=precision)
  bool operator<=(const my_type& r) const {
    return !(r < *this);
  }
  // O(N) (N=precision)
  bool operator>=(const my_type& r) const {
    return !(*this < r);
  }
  // O(N) (N=precision)
  bool operator==(const my_type& r) const {
    if((sign || r.sign) && !(sign && r.sign)) return false;
    return D == r.D;
  }
  // O(N) (N=precision)
  bool operator!=(const my_type& r) const {
    return !(*this==r);
  }
  // O(N^2 log y) (N=precision)
  my_type pow(unsigned long long y) const {
    if(y==0){
      my_type res;
      res.set_digit(0,1);
      return res;
    }
    if(y==1) return *this;
    my_type res = pow(y/2);
    res *= res;
    if(y%2) res *= *this;
    return res;
  }
  // O(N) (N=precision)
  bool is_zero() const {
    for(int i=0; i<array_size; i++) if(D[i]!=0) return false;
    return true;
  }
  // O(N^2) (N=precision)
  my_type& operator/=(const my_type& r){
    assert(!r.is_zero());
    if(is_zero()) return *this;
    my_type res;
    number_type buf; buf.fill(0);
    digit_type msb_base=1; while(msb_base<base) msb_base=(msb_base<<1)|(digit_type)1;
    msb_base&=~(msb_base>>1);
    digit_type overflow=0;
    for(int i=array_size+decimal_size-1; i>=0; i--){
      overflow = buf[array_size-1];
      for(int j=array_size-1; j>=0; j--) buf[j+1]=buf[j];
      if(i>=decimal_size) buf[0]=D[i-decimal_size];
      digit_type digit=0;
      for(digit_type t=msb_base; t; t>>=1){
        number_type t_rD;
        digit_type bufoverflow=digit_multyply_unsigned(t_rD,r.D,t);
        while((overflow>bufoverflow)?true:(overflow==bufoverflow && !cmp_unsigned(buf,t_rD))){
          number_type bufbuf;
          overflow -= bufoverflow;
          if(subtract_unsigned(bufbuf,buf,t_rD)) overflow--;
          buf = bufbuf;
          digit+=t;
        }
      }
      if(i>=array_size) assert(digit==0);
      else res.D[i]=digit;
    }
    number_type lsbbuf=r.D; half_unsigned(lsbbuf);
    if(cmp_unsigned(lsbbuf,buf)) assert(!add_lsb_unsigned(res.D));
    res.sign = multiply_sign(sign,r.sign);
    return *this = res;
  }
  // O(N) (N=precision)
  my_type abs() const { return (sign==sign_pos) ? *this : -*this; }
  // O(N) (N=precision)
  my_type floor() const {
    my_type res=*this;
    bool hit_digit=false;
    for(int i=0; i<decimal_size; i++){ hit_digit=res.D[i]!=0; res.D[i]=0; }
    if(sign==sign_neg) if(hit_digit) res+=my_type("-1");
    return res;
  }
  // O(N) (N=precision)
  my_type ceil() const {
    my_type res=*this;
    res.sign=!res.sign;
    res=res.floor();
    res.sign=!res.sign;
    return res;
  }
  // O(N^2) (N=precision)
  my_type mod(my_type div) const {
    return *this - (*this / div).floor() * div;
  }
  // O(N^3) (N=precision)
  my_type exp() const {
    my_type intidx = floor();
    my_type x = *this - intidx;
    my_type buf = 1;
    my_type res = 0;
    for(int i=0; !buf.is_zero(); i++){
      res += buf;
      buf *= x;
      buf /= (i+1);
    }
    while(!intidx.is_zero()) buf *= NAPIER;
    return res;
  }
  // O(N^3) (N=precision)
  my_type cos() const {
    my_type x = mod(PI * my_type(2));
    my_type buf = 1;
    my_type res = 0;
    for(int i=0; !buf.is_zero(); i+=2){
      res += buf;
      buf *= -x*x;
      buf /= (i+1)*(i+2);
    }
    return res;
  }
  // O(N^3) (N=precision)
  my_type sin() const {
    my_type x = mod(PI * my_type(2));
    my_type buf = x;
    my_type res = 0;
    for(int i=1; !buf.is_zero(); i+=2){
      res += buf;
      buf *= -x*x;
      buf /= (i+1)*(i+2);
    }
    return res;
  }
  // O(N^3) (N=precision)
  my_type atan() const {
    if(my_type("0.5") < *this) return PI/4.0+((*this-1)/(*this+1)).atan();
    if(my_type("2.4") < *this) return PI/2.0-(my_type("1") / *this).atan();
    my_type x = -*this * *this;
    my_type buf = *this;
    my_type res = 0;
    for(int i=1; !buf.is_zero(); i+=2){
      res += buf / i;
      buf *= x;
    }
    return res;
  }
  sign_type get_sign() const { return sign; }
  number_type get_digits() const { return D; }
};

const basic_fixed_decimal::my_type basic_fixed_decimal::PI = (basic_fixed_decimal("0.2").atan() * 4.0 - (basic_fixed_decimal("1") / basic_fixed_decimal("239")).atan()) * 4.0;
const basic_fixed_decimal::my_type basic_fixed_decimal::NAPIER = basic_fixed_decimal("0.5").exp().pow(2);
constexpr base_power_class<basic_fixed_decimal::digit_type,basic_fixed_decimal::index_type,basic_fixed_decimal::min_base,basic_fixed_decimal::base_size> basic_fixed_decimal::base_power;




std::ostream& operator<<(std::ostream& ostr,const basic_fixed_decimal& a){
  return ostr<<a.to_string();
}

std::istream& operator>>(std::istream& istr,basic_fixed_decimal& a){
  std::string buf; istr>>buf;
  if(!istr.good()) return istr;
  a = basic_fixed_decimal(buf);
  return istr;
}

using fixdec=basic_fixed_decimal;


#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

int N,K;
fixdec X[18];
set<fixdec> S;

int popcount(int x){ int res=0; rep(d,18) res+=(x>>d)&1; return res; }

int main(){
  cin>>N>>K;
  rep(i,N) cin>>X[i];
  rep(i,1<<N) if(popcount(i)>=K){ fixdec a("0"); rep(d,N) if((i>>d)&1) a+=X[d]; S.insert(a); }
  rep(i,1<<N) if(popcount(i)>=K){ fixdec a("1"); rep(d,N) if((i>>d)&1) a*=X[d]; S.insert(a); }
  cout<<S.size()<<"\n";
  return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード