結果
| 問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
| ユーザー |
👑  kakel-san
|
| 提出日時 | 2023-08-02 23:52:20 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,484 bytes |
| コンパイル時間 | 1,017 ms |
| コンパイル使用メモリ | 118,204 KB |
| 実行使用メモリ | 67,276 KB |
| 最終ジャッジ日時 | 2024-04-20 23:44:29 |
| 合計ジャッジ時間 | 10,190 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 32 ms
33,160 KB |
| testcase_01 | TLE | - |
| testcase_02 | TLE | - |
| testcase_03 | TLE | - |
| testcase_04 | TLE | - |
| testcase_05 | TLE | - |
| testcase_06 | TLE | - |
| testcase_07 | TLE | - |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| testcase_10 | TLE | - |
| testcase_11 | TLE | - |
| testcase_12 | TLE | - |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
| testcase_17 | TLE | - |
| testcase_18 | TLE | - |
| testcase_19 | TLE | - |
| testcase_20 | TLE | - |
| testcase_21 | TLE | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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 tree
public 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);
}
}
}