#870615 (C++23) No.2308 [Cherry 5th Tune B] もしかして、真?

提出ソース

結果

問題	No.2308 [Cherry 5th Tune B] もしかして、真?
ユーザー
提出日時	2023-05-19 22:50:03
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	9,104 bytes
コンパイル時間	3,402 ms
コンパイル使用メモリ	252,088 KB
実行使用メモリ	12,032 KB
最終ジャッジ日時	2024-05-10 06:17:07
合計ジャッジ時間	14,852 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	AC	268 ms 7,760 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	AC	264 ms 7,752 KB
testcase_21	WA	-
testcase_22	AC	286 ms 11,776 KB
testcase_23	AC	286 ms 11,904 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	283 ms 11,904 KB
testcase_27	AC	289 ms 11,776 KB
testcase_28	AC	282 ms 12,032 KB
testcase_29	WA	-
testcase_30	AC	285 ms 11,880 KB
testcase_31	AC	237 ms 11,880 KB
testcase_32	AC	236 ms 11,776 KB
testcase_33	AC	234 ms 11,776 KB
testcase_34	AC	254 ms 11,904 KB
testcase_35	WA	-
testcase_36	AC	255 ms 11,904 KB
testcase_37	WA	-
testcase_38	WA	-

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

using ull = uint64_t;
using ll = int64_t;
using vi = vector<int>;
using vll = vector<ll>;
using vs = vector<string>;
using ld = long double;
using P = pair<ll,ll>;
using G = vector<vector<int>>;

#define LO(...) (void)0
#define debug(x) (void)0

#define reps(i,a,n) for(ll i##_len = (ll)(n), i = (a); i < i##_len; ++i)
#define rep(i,n) reps(i,0,(n))
#define rrep(i,n) reps(i,1,(n)+1)
#define repd(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrepd(i,n) for(ll i=(n);i>=1;i--)

namespace std {template<typename T,typename U> istream &operator>>(istream &is, pair<T,U> &v){return is>>v.first>>v.second;}}

template<typename T>void input(T& a){cin>>a;}
template<typename T,typename... Ts>void input(T& a,Ts&... b){cin>>a;input(b...);}
#define inp(...) ll __VA_ARGS__;input(__VA_ARGS__)
#define inps(...) string __VA_ARGS__;input(__VA_ARGS__)
#define inpp(p) cin >> (p).first >> (p).second
#define inpv(v,N) vll v(N);rep(i,N)cin>>v[i];
#define inpvs(v,N) vs v(N);rep(i,N)cin>>v[i];
#define all(v) begin(v),end(v)
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define allok(i,N,pred) [&]()->bool{bool allok_=1;rep(i,N)if(!(pred))allok_=0;return allok_;}()
#define anyok(i,N,pred) [&]()->bool{bool anyok_=0;rep(i,N)if(pred)anyok_=1;return anyok_;}()
inline void YESNO(bool b){cout<<(b?"YES\n":"NO\n");}inline void yesno(bool b){cout<<(b?"yes\n":"no\n");}inline void YesNo(bool b){cout<<(b?"Yes\n":"No\n");}

#define SP cout<<' '
#define ENDL cout<<'\n'
#define setfp cout<<fixed<<setprecision(16)
template<typename C>string join(const C &v){ostringstream s;bool f=1;for(auto &&e:v){if(!f)s<<' ';f=0;s<<e;}return s.str();}
template<typename C>string joinadd(const C &v){ostringstream s;bool f=1;for(auto &&e:v){if(!f)s<<' ';f=0;s<<e+1;}return s.str();}
template<typename C>void prv_(const C &v){cout<<join(v);}
template<typename C>void prvadd_(const C &v){cout<<joinadd(v);}
template<typename C>void prv(const C &v){prv_(v);ENDL;}
template<typename C>void prvadd(const C &v){prvadd_(v);ENDL;}

template<typename ...>using rr_void_t=void;
template<typename T,typename=void>struct is_container:false_type{};
template<typename T>struct is_container<T,rr_void_t<typename T::iterator>>:true_type{};

template<typename T,typename=enable_if_t<is_container<T>::value && !is_same<string,T>::value>>
void pr_(const T& a){prv_(a);}
template<typename T,typename=enable_if_t<!is_container<T>::value || is_same<string,T>::value>,typename=void>
void pr_(const T& a){cout<<a;}
inline void pr(){cout<<'\n';}
template<typename T>void pr(const T& a){pr_(a);cout<<'\n';}
template<typename T,typename... Ts>void pr(const T& a,const Ts&... b){pr_(a);cout<<' ';pr(b...);}
template<typename T>void prs(const T& a){pr_(a);SP;}

inline ll max(ll a, ll b){return max<ll>(a, b);}
inline ll min(ll a, ll b){return min<ll>(a, b);}
template<typename T>bool chmax(T &a,const T &b){return a<b?(a=b,1):0;}
template<typename T>bool chmin(T &a,const T &b){return b<a?(a=b,1):0;}

template<typename T,typename C=less<>>void so(T &a,C c=C{}){sort(begin(a),end(a),c);}
template<typename T,typename C=less<>>void rso(T &a,C c=C{}){sort(rbegin(a),rend(a),c);}
template<typename T>void rev(T &a){reverse(begin(a),end(a));}

constexpr ll INF = 1e18;
#ifndef ATCODER_FENWICKTREE_HPP
#define ATCODER_FENWICKTREE_HPP 1

#include <cassert>
#include <vector>

#ifndef ATCODER_INTERNAL_TYPE_TRAITS_HPP
#define ATCODER_INTERNAL_TYPE_TRAITS_HPP 1

#include <cassert>
#include <numeric>
#include <type_traits>

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              std::true_type,
                                              std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
    typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<is_integral<T>::value &&
                                  std::is_unsigned<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
                                              std::make_unsigned<T>,
                                              std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder

#endif  // ATCODER_INTERNAL_TYPE_TRAITS_HPP

namespace atcoder {

// Reference: https://en.wikipedia.org/wiki/Fenwick_tree
template <class T> struct fenwick_tree {
    using U = internal::to_unsigned_t<T>;

  public:
    fenwick_tree() : _n(0) {}
    explicit fenwick_tree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p && p < _n);
        p++;
        while (p <= _n) {
            data[p - 1] += U(x);
            p += p & -p;
        }
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }

  private:
    int _n;
    std::vector<U> data;

    U sum(int r) {
        U s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};

}  // namespace atcoder

#endif  // ATCODER_FENWICKTREE_HPP

int main() {
    inp(T);
    while(T--){
        inp(N);
        vll a(N);
        rep(i,N){
            inps(X);
            a[i] = X=="True";
        }

        inpvs(Y,N-1);
        atcoder::fenwick_tree<int> fen(N-1);
        rep(i,N-1){
            inp(s);
            s--;

            ll ok = 0;
            ll ng = N-1-i;

            while(abs(ng - ok) > 1){
                ll mid = ok + (ng - ok) / 2;

                ll k = fen.sum(0, mid+1);

                bool isOk = mid - k <= s;
                if(isOk) ok = mid;
                else ng = mid;
            }

            ll ok1 = ok;

            ok = 0;
            ng = N-1-i;

            while(abs(ng - ok) > 1){
                ll mid = ok + (ng - ok) / 2;

                ll k = fen.sum(0, mid+1);

                bool isOk = mid - k <= s+1;
                if(isOk) ok = mid;
                else ng = mid;
            }

            if(Y[ok1] == "and"){
                a[ok1] = a[ok1] & a[ok];
            }else if(Y[ok1] == "or"){
                a[ok1] = a[ok1] | a[ok];
            }else if(Y[ok1] == "xor"){
                a[ok1] = a[ok1] ^ a[ok];
            }else if(Y[ok1] == "imp"){
                if(a[ok1]){
                    a[ok1] = a[ok];
                }else{
                    a[ok1] = 1;
                }
            }
            fen.add(ok, 1);
        }
        pr(a[0] ? "True" : "False");
    }
}

yukicoder

結果

テストケース

ソースコード