結果
問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
ユーザー |
|
提出日時 | 2023-05-24 10:14:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 847 ms / 2,000 ms |
コード長 | 5,706 bytes |
コンパイル時間 | 2,221 ms |
コンパイル使用メモリ | 207,804 KB |
最終ジャッジ日時 | 2025-02-13 04:24:09 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define SZ(x) (int) (x).size()#define REP(i, n) for(int i = 0; i < (n); i++)#define FOR(i, a, b) for(auto i = (a); i < (b); i++)#define For(i, a, b, c) \for(auto i = (a); i != (b); i += (c))#define REPR(i, n) for(auto i = (n) -1; i >= 0; i--)#define ALL(s) (s).begin(), (s).end()#define so(V) sort(ALL(V))#define rev(V) reverse(ALL(V))#define uni(v) v.erase(unique(ALL(v)), (v).end())#define eb emplace_backtypedef unsigned long long ull;typedef long long ll;typedef vector<int> vi;typedef vector<ll> vll;typedef vector<bool> vb;typedef vector<vi> vvi;typedef vector<vll> vvll;typedef pair<int, int> PI;typedef pair<ll, ll> PL;const double EPS = 1e-6;const int MOD = 1e9 + 7;const int INF = (1 << 30);const ll LINF = 1e18;const double math_PI = acos(-1);template<typename T>vector<T> make_v(size_t a) {return vector<T>(a);}template<typename T, typename... Ts>auto make_v(size_t a, Ts... ts) {return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));}template<typename T, typename V>typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) {t = v;}template<typename T, typename V>typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) {for(auto& e: t) fill_v(e, v);}template<class T>bool chmax(T& a, const T& b) {if(a < b) {a = b;return true;}return false;}template<class T>bool chmin(T& a, const T& b) {if(a > b) {a = b;return true;}return false;}template<typename S, typename T>istream& operator>>(istream& is, pair<S, T>& p) {cin >> p.first >> p.second;return is;}template<typename T>istream& operator>>(istream& is, vector<T>& vec) {for(T& x: vec) is >> x;return is;}template<typename T>string join(vector<T>& vec, string splitter) {stringstream ss;REP(i, SZ(vec)) {if(i != 0) ss << splitter;ss << vec[i];}return ss.str();}template<typename T>ostream& operator<<(ostream& os, vector<T>& vec) {os << join(vec, " ");return os;}template<typename T, int MAX_LOG = 32>struct BinaryTrie {struct Node {vi next; //谺。縺ョ鬆らせ逡ェ蜿キint common; //縺薙・鬆らせ繧帝·壹k譁・ュ怜・縺ョ謨ーT lazy;Node() {next.assign(2, -1);common = 0;lazy = 0;}};vector<Node> nodes;BinaryTrie() {nodes.push_back(Node());}void apply_xor(T val) {nodes[0].lazy ^= val;}private:void push(int cur, int b) {if((nodes[cur].lazy >> (T) b) & (T) 1) {swap(nodes[cur].next[0], nodes[cur].next[1]);}REP(i, 2) {if(nodes[cur].next[i] != -1) {nodes[nodes[cur].next[i]].lazy^= nodes[cur].lazy;}}nodes[cur].lazy = 0;}public:void add(T val, int cur = 0, int b = MAX_LOG - 1) {nodes[cur].common++;if(b < 0) {return;}push(cur, b);int nxt = (val >> (T) b) & (T) 1;if(nodes[cur].next[nxt] == -1) {nodes[cur].next[nxt] = SZ(nodes);nodes.push_back(Node());}add(val, nodes[cur].next[nxt], b - 1);}void erase(T val, int cur = 0, int b = MAX_LOG - 1) {assert(cur != -1);nodes[cur].common--;if(b < 0) {return;}push(cur, b);int nxt = (val >> (T) b) & (T) 1;erase(val, nodes[cur].next[nxt], b - 1);}T min_element(T bxor = 0, int cur = 0,int b = MAX_LOG - 1) {if(b < 0) return 0;push(cur, b);int nxt = (bxor >> (T) b) & (T) 1;int ind = nodes[cur].next[nxt];if(ind == -1 || nodes[ind].common == 0) {nxt = nxt ^ 1;}return min_element(bxor, nodes[cur].next[nxt],b - 1)| ((T) nxt << (T) b);}T max_element(T bxor = 0) {return min_element(~bxor);}int lower_bound_rank(T val, int cur = 0,int b = MAX_LOG - 1) {if(cur == -1 || b < 0) return 0;push(cur, b);int nxt = (val >> (T) b) & (T) 1;int ret = lower_bound_rank(val, nodes[cur].next[nxt], b - 1);if(nxt == 1 && nodes[cur].next[0] != -1) {ret += nodes[nodes[cur].next[0]].common;}return ret;}int upper_bound_rank(T val) {return lower_bound_rank(val + 1);}T kth_smallest(int k, int cur = 0,int b = MAX_LOG - 1) {if(b < 0) return 0;int lower_ind = nodes[cur].next[0];int lower_cnt = 0;if(lower_ind != -1) {lower_cnt = nodes[lower_ind].common;}if(k < lower_cnt) {return kth_smallest(k, nodes[cur].next[0],b - 1);} else {return kth_smallest(k - lower_cnt,nodes[cur].next[1], b - 1)| ((T) 1 << (T) b);}}T kth_largest(int k) {return kth_smallest(SZ(size()) - 1 - k);}T operator[](int k) {return kth_smallest(k);}int count(T val) {int cur = 0;REPR(b, MAX_LOG) {push(cur, b);cur = nodes[cur].next[(val >> (T) b) & (T) 1];if(cur == -1) return 0;}return nodes[cur].common;}size_t size() const {return nodes[0].common;}bool empty() const {return nodes[0].common == 0;}};void solve() {int N;cin >> N;vector<string> X(N), Y(N - 1);cin >> X >> Y;vi S(N - 1);cin >> S;BinaryTrie<int> bX, bY;REP(i, N) {bX.add(i);if(i + 1 != N) {bY.add(i);}}REP(i, N - 1) {int p = bX.kth_smallest(S[i] - 1);int q = bX.kth_smallest(S[i]);int k = bY.kth_smallest(S[i] - 1);bool bp = (X[p] == "True");bool bq = (X[q] == "True");bool ans;if(Y[k] == "and")ans = bp & bq;else if(Y[k] == "or")ans = bp | bq;else if(Y[k] == "xor")ans = bp ^ bq;elseans = (!bp) | bq;if(ans) {X[p] = "True";} else {X[p] = "False";}bX.erase(q);bY.erase(k);}cout << X[bX[0]] << endl;}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);int T;cin >> T;while(T--) {solve();}return 0;}