結果
| 問題 |
No.2308 [Cherry 5th Tune B] もしかして、真?
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2023-05-19 22:50:03 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,104 bytes |
| コンパイル時間 | 3,819 ms |
| コンパイル使用メモリ | 253,260 KB |
| 実行使用メモリ | 11,912 KB |
| 最終ジャッジ日時 | 2024-12-20 01:22:12 |
| 合計ジャッジ時間 | 15,218 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 14 WA * 25 |
ソースコード
#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");
}
}