結果
問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
ユーザー | Daylight |
提出日時 | 2023-05-24 10:14:53 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 960 ms / 2,000 ms |
コード長 | 5,706 bytes |
コンパイル時間 | 2,496 ms |
コンパイル使用メモリ | 212,512 KB |
実行使用メモリ | 69,560 KB |
最終ジャッジ日時 | 2023-08-25 02:40:10 |
合計ジャッジ時間 | 38,337 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 627 ms
22,832 KB |
testcase_02 | AC | 817 ms
39,140 KB |
testcase_03 | AC | 726 ms
35,372 KB |
testcase_04 | AC | 743 ms
38,612 KB |
testcase_05 | AC | 774 ms
39,504 KB |
testcase_06 | AC | 814 ms
54,356 KB |
testcase_07 | AC | 828 ms
54,244 KB |
testcase_08 | AC | 852 ms
57,908 KB |
testcase_09 | AC | 862 ms
56,832 KB |
testcase_10 | AC | 764 ms
36,532 KB |
testcase_11 | AC | 851 ms
39,780 KB |
testcase_12 | AC | 850 ms
40,048 KB |
testcase_13 | AC | 840 ms
39,156 KB |
testcase_14 | AC | 861 ms
39,592 KB |
testcase_15 | AC | 861 ms
39,148 KB |
testcase_16 | AC | 872 ms
39,404 KB |
testcase_17 | AC | 859 ms
39,216 KB |
testcase_18 | AC | 867 ms
40,276 KB |
testcase_19 | AC | 858 ms
39,520 KB |
testcase_20 | AC | 856 ms
41,568 KB |
testcase_21 | AC | 943 ms
67,984 KB |
testcase_22 | AC | 960 ms
67,516 KB |
testcase_23 | AC | 949 ms
68,400 KB |
testcase_24 | AC | 941 ms
67,004 KB |
testcase_25 | AC | 941 ms
67,516 KB |
testcase_26 | AC | 951 ms
67,632 KB |
testcase_27 | AC | 942 ms
66,288 KB |
testcase_28 | AC | 934 ms
66,520 KB |
testcase_29 | AC | 941 ms
68,620 KB |
testcase_30 | AC | 956 ms
67,088 KB |
testcase_31 | AC | 435 ms
66,860 KB |
testcase_32 | AC | 432 ms
66,796 KB |
testcase_33 | AC | 427 ms
67,212 KB |
testcase_34 | AC | 453 ms
68,548 KB |
testcase_35 | AC | 448 ms
67,164 KB |
testcase_36 | AC | 444 ms
69,560 KB |
testcase_37 | AC | 62 ms
4,376 KB |
testcase_38 | AC | 859 ms
39,120 KB |
ソースコード
#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_back typedef 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; else ans = (!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; }