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

提出ソース

結果

問題	No.2308 [Cherry 5th Tune B] もしかして、真?
ユーザー	norikame
提出日時	2023-05-19 22:59:37
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	609 ms / 2,000 ms
コード長	1,947 bytes
コンパイル時間	5,980 ms
コンパイル使用メモリ	319,540 KB
実行使用メモリ	18,192 KB
最終ジャッジ日時	2023-08-23 01:00:27
合計ジャッジ時間	30,057 ms
ジャッジサーバーID （参考情報）	judge14 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	489 ms 7,944 KB
testcase_02	AC	560 ms 10,452 KB
testcase_03	AC	517 ms 10,556 KB
testcase_04	AC	522 ms 11,196 KB
testcase_05	AC	521 ms 11,688 KB
testcase_06	AC	547 ms 14,360 KB
testcase_07	AC	550 ms 13,560 KB
testcase_08	AC	570 ms 15,552 KB
testcase_09	AC	563 ms 15,488 KB
testcase_10	AC	527 ms 10,928 KB
testcase_11	AC	550 ms 11,120 KB
testcase_12	AC	550 ms 10,936 KB
testcase_13	AC	563 ms 10,900 KB
testcase_14	AC	552 ms 10,824 KB
testcase_15	AC	554 ms 11,100 KB
testcase_16	AC	550 ms 10,832 KB
testcase_17	AC	550 ms 10,816 KB
testcase_18	AC	552 ms 11,128 KB
testcase_19	AC	552 ms 10,820 KB
testcase_20	AC	547 ms 10,952 KB
testcase_21	AC	606 ms 17,808 KB
testcase_22	AC	600 ms 18,192 KB
testcase_23	AC	605 ms 17,800 KB
testcase_24	AC	604 ms 17,760 KB
testcase_25	AC	607 ms 17,752 KB
testcase_26	AC	602 ms 18,080 KB
testcase_27	AC	606 ms 17,756 KB
testcase_28	AC	607 ms 18,188 KB
testcase_29	AC	609 ms 17,800 KB
testcase_30	AC	604 ms 17,808 KB
testcase_31	AC	439 ms 17,816 KB
testcase_32	AC	433 ms 18,128 KB
testcase_33	AC	436 ms 17,812 KB
testcase_34	AC	473 ms 17,808 KB
testcase_35	AC	476 ms 18,136 KB
testcase_36	AC	474 ms 18,144 KB
testcase_37	AC	27 ms 4,376 KB
testcase_38	AC	558 ms 10,960 KB

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

ソースコード

raw source code

// 

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

using ll = long long;

#define rep(i, n) for (int i=0; i<(int)(n); ++(i))
#define rep3(i, m, n) for (int i=(m); (i)<(int)(n); ++(i))
#define repr(i, n) for (int i=(int)(n)-1; (i)>=0; --(i))
#define rep3r(i, m, n) for (int i=(int)(n)-1; (i)>=(int)(m); --(i))
#define all(x) (x).begin(), (x).end()

const int INF = (int)(1e9);
const vector<string> ops = { "and", "or", "xor", "imp" }, bins = { "False", "True" };
const vector<vector<int>> results = {
	{ 0, 0, 0, 1 }, { 0, 1, 1, 1 }, { 0, 1, 1, 0 }, { 1, 1, 0, 1 }
};

int main() {
	int t0;
	cin >> t0;
	rep(i0, t0) {
		int n;
		cin >> n;
		vector<string> a(n*2-1);
		vector<int> s(n-1);
		rep(i, n) cin >> a[i*2];
		rep(i, n-1) cin >> a[i*2+1];
		rep(i, n-1) {
			cin >> s[i];
			s[i]--;
		}
		fenwick_tree<int> ft(n*2-1);
		rep(i, n*2-1) ft.add(i, 1);
		function<string(int)> get = [&](int id) {
			int li = -1, ri = n*2-1;
			while (ri-li > 1) {
				int ci = li + (ri-li) / 2;
				if (ft.sum(0, ci+1) > id) ri = ci;
				else li = ci;
			}
			return a[ri];
		};
		function<void(int,string)> set = [&](int id, string val) {
			int li = -1, ri = n*2-1;
			while (ri-li > 1) {
				int ci = li + (ri-li) / 2;
				if (ft.sum(0, ci+1) > id) ri = ci;
				else li = ci;
			}
			a[ri] = val;
		};
		function<void(int)> del = [&](int id) {
			int li = -1, ri = n*2-1;
			while (ri-li > 1) {
				int ci = li + (ri-li) / 2;
				if (ft.sum(0, ci+1) > id) ri = ci;
				else li = ci;
			}
			a[ri] = "";
			ft.add(ri, -1);
		};
		string res;
		rep(i, n-1) {
			string lval = get(s[i]*2), cval = get(s[i]*2+1), rval = get(s[i]*2+2);
			int oid = find(all(ops), cval) - ops.begin(), vid = (lval == "True" ? 2 : 0) + (rval == "True" ? 1 : 0);
			string bval = bins[results[oid][vid]];
			set(s[i]*2, bval);
			del(s[i]*2+2);
			del(s[i]*2+1);
			if (i == n-2) res = bval;
		}
		cout << res << endl;
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード