結果
問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
ユーザー |
|
提出日時 | 2023-08-02 23:52:43 |
言語 | C# (.NET 8.0.404) |
結果 |
TLE
|
実行時間 | - |
コード長 | 11,484 bytes |
コンパイル時間 | 18,882 ms |
コンパイル使用メモリ | 167,976 KB |
実行使用メモリ | 117,632 KB |
最終ジャッジ日時 | 2024-10-12 22:03:34 |
合計ジャッジ時間 | 40,701 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 TLE * 11 -- * 27 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (99 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;using static System.Console;using System.Linq;using System.Collections.Generic;class Program{static int NN => int.Parse(ReadLine());static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();static string[] SList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => ReadLine()).ToArray();public static void Main(){Solve();// Test();}static void Test(){var r = new Random();var n = 100000;var x = new string[n];for (var i = 0; i < x.Length; ++i) x[i] = r.Next(2) == 0 ? "True" : "False";var y = new string[n];for (var i = 0; i < y.Length; ++i){switch(r.Next(4)){case 0:y[i] = "and";break;case 1:y[i] = "or";break;case 2:y[i] = "xor";break;default:y[i] = "imp";break;}}var s = new int[n - 1];for (var i = 0; i < s.Length; ++i) s[i] = r.Next(n - 2 - i) + 1;var begin = DateTime.Now;WriteLine(IsTrue(n, x, y, s));WriteLine((DateTime.Now - begin).TotalSeconds);}static void Solve(){var t = NN;var ans = new string[t];for (var u = 0; u < t; ++u){var n = NN;var x = ReadLine().Split();var y = ReadLine().Split();var s = NList;ans[u] = IsTrue(n, x, y, s);}WriteLine(string.Join("\n", ans));}static string IsTrue(int n, string[] x, string[] y, int[] s){var xset = new CSet<Pair>();var yset = new CSet<Pair>();for (var i = 0; i < x.Length; ++i){xset.Insert(new Pair(i, x[i] == "False" ? 0 : 1));}for (var i = 0; i < y.Length; ++i){yset.Insert(new Pair(i, Decode(y[i])));}foreach (var si in s){var a = xset.ElementAt(si - 1);var op = yset.ElementAt(si - 1);var b = xset.ElementAt(si);xset.Remove(b);yset.Remove(op);a.Val = Calc(a.Val, b.Val, op.Val);}return xset.ElementAt(0).Val == 0 ? "False" : "True";}static int Decode(string s){switch (s){case "and": return 0;case "or" : return 1;case "xor": return 2;default: return 3;}}static int Calc(int a, int b, int op){switch (op){case 0: return a & b;case 1: return a | b;case 2: return a ^ b;default: return 1 - a | b;}}class Pair : IComparable{public int Pos;public int Val;public Pair(int pos, int val){Pos = pos; Val = val;}public int CompareTo(object b){return Pos.CompareTo(((Pair)b).Pos);}}public class CSet<T> where T : IComparable{protected SB_BST<T>.Node _root;public T this[int idx]{ get { return ElementAt(idx); } }public int Count(){return SB_BST<T>.Count(_root);}public virtual void Insert(T v){if (_root == null) _root = new SB_BST<T>.Node(v);else{if (SB_BST<T>.Find(_root, v) != null) return;_root = SB_BST<T>.Insert(_root, v);}}public void Clear(){_root = null;}public void Remove(T v){_root = SB_BST<T>.Remove(_root, v);}public bool Contains(T v){return SB_BST<T>.Contains(_root, v);}public T ElementAt(int k){var node = SB_BST<T>.FindByIndex(_root, k);if (node == null) throw new IndexOutOfRangeException();return node.Value;}public int Count(T v){return SB_BST<T>.UpperBound(_root, v) - SB_BST<T>.LowerBound(_root, v);}/// <summary>指定した値以上の要素のうち最小のインデックスを取得</summary>public int LowerBound(T v){return SB_BST<T>.LowerBound(_root, v);}/// <summary>指定した値より大きい要素のうち最小のインデックスを取得</summary>public int UpperBound(T v){return SB_BST<T>.UpperBound(_root, v);}public Tuple<int, int> EqualRange(T v){if (!Contains(v)) return new Tuple<int, int>(-1, -1);return new Tuple<int, int>(SB_BST<T>.LowerBound(_root, v), SB_BST<T>.UpperBound(_root, v) - 1);}public List<T> ToList(){return new List<T>(SB_BST<T>.Enumerate(_root));}}public class CMultiSet<T> : CSet<T> where T : IComparable{public override void Insert(T v){if (_root == null) _root = new SB_BST<T>.Node(v);else _root = SB_BST<T>.Insert(_root, v);}}public class SB_BST<T> where T : IComparable{public class Node{public T Value;public Node LChild;public Node RChild;public int Count; //size of the sub treepublic Node(T v){Value = v;Count = 1;}}static Random _rnd = new Random();public static int Count(Node t){return t == null ? 0 : t.Count;}static Node Update(Node t){t.Count = Count(t.LChild) + Count(t.RChild) + 1;return t;}public static Node Merge(Node l, Node r){if (l == null || r == null) return l == null ? r : l;if ((double)Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble()){l.RChild = Merge(l.RChild, r);return Update(l);}else{r.LChild = Merge(l, r.LChild);return Update(r);}}/// <summary>/// split as [0, k), [k, n)/// </summary>public static Tuple<Node, Node> Split(Node t, int k){if (t == null) return new Tuple<Node, Node>(null, null);if (k <= Count(t.LChild)){var s = Split(t.LChild, k);t.LChild = s.Item2;return new Tuple<Node, Node>(s.Item1, Update(t));}else{var s = Split(t.RChild, k - Count(t.LChild) - 1);t.RChild = s.Item1;return new Tuple<Node, Node>(Update(t), s.Item2);}}public static Node Remove(Node t, T v){if (Find(t, v) == null) return t;return RemoveAt(t, LowerBound(t, v));}public static Node RemoveAt(Node t, int k){var s = Split(t, k);var s2 = Split(s.Item2, 1);return Merge(s.Item1, s2.Item2);}public static bool Contains(Node t, T v){return Find(t, v) != null;}public static Node Find(Node t, T v){while (t != null){var cmp = t.Value.CompareTo(v);if (cmp > 0) t = t.LChild;else if (cmp < 0) t = t.RChild;else break;}return t;}public static Node FindByIndex(Node t, int idx){if (t == null) return null;var currentIdx = Count(t) - Count(t.RChild) - 1;while (t != null){if (currentIdx == idx) return t;if (currentIdx > idx){t = t.LChild;currentIdx -= (Count(t == null ? null : t.RChild) + 1);}else{t = t.RChild;currentIdx += (Count(t == null ? null : t.LChild) + 1);}}return null;}public static int UpperBound(Node t, T v){var torg = t;if (t == null) return -1;var ret = Int32.MaxValue;var idx = Count(t) - Count(t.RChild) - 1;while (t != null){var cmp = t.Value.CompareTo(v);if (cmp > 0){ret = Math.Min(ret, idx);t = t.LChild;idx -= (Count(t == null ? null : t.RChild) + 1);}else if (cmp <= 0){t = t.RChild;idx += (Count(t == null ? null : t.LChild) + 1);}}return ret == Int32.MaxValue ? Count(torg) : ret;}public static int LowerBound(Node t, T v){var torg = t;if (t == null) return -1;var idx = Count(t) - Count(t.RChild) - 1;var ret = Int32.MaxValue;while (t != null){var cmp = t.Value.CompareTo(v);if (cmp >= 0){if (cmp == 0) ret = Math.Min(ret, idx);t = t.LChild;if (t == null) ret = Math.Min(ret, idx);idx -= t == null ? 0 : (Count(t.RChild) + 1);}else if (cmp < 0){t = t.RChild;idx += (Count(t == null ? null : t.LChild) + 1);if (t == null) return idx;}}return ret == Int32.MaxValue ? Count(torg) : ret;}public static Node Insert(Node t, T v){var ub = LowerBound(t, v);return InsertByIdx(t, ub, v);}static Node InsertByIdx(Node t, int k, T v){var s = Split(t, k);return Merge(Merge(s.Item1, new Node(v)), s.Item2);}public static IEnumerable<T> Enumerate(Node t){var ret = new List<T>();Enumerate(t, ret);return ret;}static void Enumerate(Node t, List<T> ret){if (t == null) return;Enumerate(t.LChild, ret);ret.Add(t.Value);Enumerate(t.RChild, ret);}}}