結果
| 問題 |
No.2308 [Cherry 5th Tune B] もしかして、真?
|
| コンテスト | |
| ユーザー |
 kwm_t
|
| 提出日時 | 2023-05-20 10:59:58 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,153 ms / 2,000 ms |
| コード長 | 5,677 bytes |
| コンパイル時間 | 2,524 ms |
| コンパイル使用メモリ | 213,744 KB |
| 最終ジャッジ日時 | 2025-02-13 03:40:53 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 39 |
ソースコード
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
struct trie {
int kind;
vector<int>node;
vector<vector<int>>next;
vector<bool>end;
trie(int _kind) :kind(_kind) {
node.resize(1);
end.resize(1);
next.emplace_back(vector<int>(kind, -1));
}
void insert(const vector<int>&v) {
int now = 0;
rep(i, v.size()) {
if (-1 == next[now][v[i]]) {
next[now][v[i]] = node.size();
node.emplace_back(0);
end.push_back(false);
next.emplace_back(vector<int>(kind, -1));
}
now = next[now][v[i]];
node[now]++;
}
end[now] = true;
}
// prefixも投入する
void insertEx(const vector<int>&v) {
int now = 0;
rep(i, v.size()) {
if (-1 == next[now][v[i]]) {
next[now][v[i]] = node.size();
node.emplace_back(0);
next.emplace_back(vector<int>(kind, -1));
}
now = next[now][v[i]];
node[now] += v.size() - i;
end[now] = true;
}
}
// 1-indexed
vector<int>kth_element(int k) {
int now = 0;
vector<int>ret;
while (true) {
bool flag = false;
rep(i, kind) {
if (-1 == next[now][i])continue;
if (k <= node[next[now][i]]) {
flag = true;
ret.emplace_back(i);
now = next[now][i];
break;
}
else {
k -= node[next[now][i]];
}
}
if (!flag)break;
}
return ret;
}
bool seach(const vector<int>&v) {
int now = 0;
rep(i, v.size()) {
if (-1 == next[now][v[i]])return false;
if (node[next[now][v[i]]] <= 0)return false;
now = next[now][v[i]];
}
return end[now];
}
void erase(const vector<int>&v) {
int now = 0;
rep(i, v.size()) {
now = next[now][v[i]];
node[now]--;
}
end[now] = false;
}
// GetIndex
int getIndex(const vector<int>&v) {
int ret = 0, now = 0;
rep(i, v.size()) {
if (0 != now) {
ret += node[now];
rep(j, 2)if (-1 != next[now][j])ret -= node[next[now][j]];
}
if (0 == v[i]) {
if (-1 == next[now][v[i]])break;
now = next[now][v[i]];
}
else {
if (-1 != next[now][0]) ret += node[next[now][0]];
if (-1 == next[now][v[i]])break;
now = next[now][v[i]];
}
}
return ret;
}
// prefixも取得する
vector<int> getIndexEx(const vector<int>&v) {
vector<int>ret;
int idx = 0, now = 0;
rep(i, v.size()) {
if (0 != now) {
idx += node[now];
rep(j, 2)if (-1 != next[now][j])idx -= node[next[now][j]];
}
if (0 == v[i]) {
if (-1 == next[now][v[i]])break;
now = next[now][v[i]];
}
else {
if (-1 != next[now][0]) idx += node[next[now][0]];
if (-1 == next[now][v[i]])break;
now = next[now][v[i]];
}
ret.push_back(idx);
}
return ret;
}
// Binary Trie
vector<int>xor_max(const vector<int>&v) {
vector<int>ret;
int now = 0;
rep(i, v.size()) {
vector<int>tmp = { 1 - v[i],v[i] };
rep(j, tmp.size()) {
if (-1 == next[now][tmp[j]])continue;
if (node[next[now][tmp[j]]] <= 0)continue;
ret.emplace_back(tmp[j]);
now = next[now][tmp[j]];
break;
}
}
return ret;
}
vector<int>xor_min(const vector<int>&v) {
vector<int>ret;
int now = 0;
rep(i, v.size()) {
vector<int>tmp = { v[i],1 - v[i] };
rep(j, tmp.size()) {
if (-1 == next[now][tmp[j]])continue;
if (node[next[now][tmp[j]]] <= 0)continue;
ret.emplace_back(tmp[j]);
now = next[now][tmp[j]];
break;
}
}
return ret;
}
// xとxorした結果がk未満になる物の数(0含む)
int xor_count(const vector<int>&x, const vector<int>&k) {
int ret = 0, now = 0;
rep(i, k.size()) {
if (0 == k[i]) {
if (-1 == next[now][x[i]])break;
now = next[now][x[i]];
}
else {
if (-1 != next[now][x[i]])ret += node[next[now][x[i]]];
if (-1 == next[now][1 - x[i]])break;
now = next[now][1 - x[i]];
}
}
return ret;
}
};
// Binary Trie
vector<int> trans(long long n, int sz = 30) {
vector<int>ret(sz, 0);
rep(i, sz) {
if (1 & (n >> i))ret[sz - 1 - i] = 1;
}
return ret;
}
long long inverse(const vector<int>&v) {
long long ret = 0;
rep(i, v.size()) {
ret *= 2;
ret += v[i];
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<bool>a(n);
vector<string>b(n - 1);
rep(i, n) {
string s; cin >> s;
if ("True" == s)a[i] = 1;
}
rep(i, n - 1)cin >> b[i];
trie tra(2);
rep(i, n) tra.insert(trans(i));
trie trb(2);
rep(i, n - 1) trb.insert(trans(i));
rep(i, n - 1) {
int t; cin >> t, t--;
auto p = inverse(tra.kth_element(t + 1));
auto q = inverse(tra.kth_element(t + 2));
auto x = inverse(trb.kth_element(t + 1));
if ("and" == b[x]) {
a[p] = a[p] & a[q];
}
else if("or" == b[x]) {
a[p] = a[p] | a[q];
}
else if("xor" == b[x]) {
a[p] = a[p] ^ a[q];
}
else {
a[p] = (a[p] ? a[q] : true);
}
tra.erase(trans(q));
trb.erase(trans(x));
}
if (a[0])cout << "True" << endl;
else cout << "False" << endl;
}
return 0;
}