結果
| 問題 |
No.2240 WAC
|
| コンテスト | |
| ユーザー |
 ushiro
|
| 提出日時 | 2023-03-10 23:29:59 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 1,621 ms / 2,000 ms |
| コード長 | 14,627 bytes |
| コンパイル時間 | 9,280 ms |
| コンパイル使用メモリ | 165,012 KB |
| 実行使用メモリ | 235,120 KB |
| 最終ジャッジ日時 | 2024-09-18 05:40:51 |
| 合計ジャッジ時間 | 31,955 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 43 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (100 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.cs(23,16): warning CS0414: フィールド 'Program.mod' が割り当てられていますが、値は使用されていません [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(17,17): warning CS0414: フィールド 'Program.inf' が割り当てられていますが、値は使用されていません [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(22,19): warning CS0414: フィールド 'Program.alpha' が割り当てられていますが、値は使用されていません [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(55,255): warning CA2200: キャッチされた例外が再スローされると、スタック情報が変更されます (https://learn.microsoft.com/dotnet/fundamentals/code-analysis/quality-rules/ca2200) [/home/judge/data/code/main.csproj] main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Program
{
#region library
static int n = 0;
static int r = 0;
static int c = 0;
static string s = "";
static long sum = 0;
static long cnt = 0;
static long max = long.MinValue;
static long min = long.MaxValue;
static long inf = long.MaxValue / 2;
static bool flg = false;
static long[] arr;
static char[,] map;
static long[,] imap;
static string alpha = "abcdefghijklmnopqrstuvwxyz";
static int mod = 1000000007;
public class Input { static readonly char[] separator = { ' ', '\r', '\n' }; readonly StreamReader sr; readonly Queue<string> queue; public Input(string path = "") { queue = new Queue<string>(); if (string.IsNullOrEmpty(path)) { sr = new StreamReader(Console.OpenStandardInput()); } else { sr = new StreamReader(path); } } public void SetText(IEnumerable<string> items) { foreach (var item in items) { SetText(item); } } public bool SetText(string s) { if (s == null) return false; foreach (var elem in s.Trim().Split(separator, StringSplitOptions.RemoveEmptyEntries)) { queue.Enqueue(elem); } return true; } public bool Any() { return queue.Any() || Read(); } bool Read() { if (!SetText(sr.ReadLine())) return false; if (!queue.Any()) return Read(); return queue.Any(); } public string Next() { if (!queue.Any() && !Read()) { return ""; } return queue.Dequeue(); } bool Accumulate(int n) { while (queue.Count() < n) { if (!Read()) return false; } return true; } public int NextInt() { return int.Parse(Next()); } public long NextLong() { return long.Parse(Next()); } public double NextDouble() { return double.Parse(Next()); } T[] NextT<T>(int n, T offset, Func<string, T> parse, Func<T, T, T> add) { if (!Accumulate(n)) return null; var a = new T[n]; for (int i = 0; i < n; i++) a[i] = add(parse(queue.Dequeue()), offset); return a; } public string[] Next(int n) { return NextT(n, "", x => x, (x, y) => x); } public int[] NextInt(int n, int offset = 0) { return NextT(n, offset, int.Parse, (x, y) => x + y); } public long[] NextLong(int n, long offset = 0) { return NextT(n, offset, long.Parse, (x, y) => x + y); } public double[] NextDouble(int n, double offset = 0.0) { return NextT(n, offset, double.Parse, (x, y) => x + y); } }
static Input input;
static int Int() { return input.NextInt(); }
static long Long() { return input.NextLong(); }
static double Double() { return input.NextDouble(); }
static string Text() { return input.Next(); }
static void wl(object obj = null) { Console.WriteLine(obj); }
static void w(object obj) { Console.Write(obj); }
static void YES() { wl("YES"); }
static void NO() { wl("NO"); }
static void YN(bool b) { if (b) YES(); else NO(); }
static void Yes() { wl("Yes"); }
static void No() { wl("No"); }
static void yn(bool b) { if (b) Yes(); else No(); }
static void Sum() { wl(sum); }
static void Cnt() { wl(cnt); }
static void Max() { wl(max); }
static void Min() { wl(min); }
static void swap<T>(ref T a, ref T b) { var w = a; a = b; b = w; }
static void SetArray(long[] array = null) { if (array != null) { for (int i = 0; i < array.Length; i++) { array[i] = Long(); } } else { if (n == 0) { n = Int(); } arr = new long[n]; for (int i = 0; i < n; i++) { arr[i] = Long(); } } }
static void ShowArray(long[] array = null) { if (array != null) { wl(string.Join(" ", array)); } else if (arr != null) { wl(string.Join(" ", arr)); } }
static void CompressArray() { var list = arr.ToList(); list = list.OrderBy(x => x).ToList(); var dic = new Dictionary<long, long>(); var cnt = 0; for (int i = 0; i < list.Count; i++) { if (!dic.ContainsKey(list[i])) { dic.Add(list[i], cnt); cnt++; } } var arr2 = new long[arr.Length]; for (int i = 0; i < arr.Length; i++) { arr2[i] = dic[arr[i]]; } arr = arr2; }
static void SetMap(char[,] map2 = null) { if (r == 0 && c == 0) { r = Int(); c = Int(); } if (map2 != null) { for (int i = 0; i < r; i++) { s = Text(); for (int j = 0; j < c; j++) { map2[i, j] = s[j]; } } } else { map = new char[r, c]; for (int i = 0; i < r; i++) { s = Text(); for (int j = 0; j < c; j++) { map[i, j] = s[j]; } } } }
static void RotateMap() { var map2 = new char[c, r]; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { map2[j, r - i - 1] = map[i, j]; } } map = map2; }
static void SetIMap(long[,] imap2 = null) { if (r == 0 && c == 0) { r = Int(); c = Int(); } if (imap2 != null) { for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { imap2[i, j] = Long(); } } } else { imap = new long[r, c]; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { imap[i, j] = Long(); } } } }
static void ShowMap(char[,] map2 = null) { for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (map2 != null) w(map2[i, j] + " "); else w(map[i, j] + " "); } wl(); } }
static void ShowIMap(long[,] imap2 = null) { for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (imap2 != null) w(imap2[i, j] + " "); else w(imap[i, j] + " "); } wl(); } }
#endregion
#region main
static void Main(string[] args) { var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(sw); input = new Input(); try { Solve(); } catch (Exception ex) { wl(ex); if (!(args.Length >= 1 && args[0] == "/debug")) throw ex; } Console.Out.Flush(); }
public static void Solve()
{
n = Int();
var m = Int();
s = Text();
var mw = new MultiSet<int>();
var ma = new MultiSet<int>();
var mc = new MultiSet<int>();
for (int i = 0; i < s.Length; i++)
{
if (s[i] == 'W') mw.Add(i);
if (s[i] == 'A') ma.Add(i);
if (s[i] == 'C') mc.Add(i);
}
flg = true;
while (mw.Count() > 0 || ma.Count() > 0 || mc.Count() > 0)
{
if (mc.Count() > 0)
{
if (mc[0] > ma[0])
{
mc.Remove(mc[0]);
ma.Remove(ma[0]);
}
else
{
flg = false;
}
}
else
{
if (mw[(int)mw.Count() - 1] < ma[(int)ma.Count() - 1])
{
mw.Remove(mw[(int)mw.Count() - 1]);
ma.Remove(ma[(int)ma.Count() - 1]);
}
else
{
flg = false;
}
}
if (!flg) break;
}
yn(flg);
}
#endregion
#region multiset
//SortedListの高速版・追加時は自動で昇順ソート・UpperBound・LowerBoundnによる検索・削除も可能
public class MultiSet<T> : Set<T> where T : IComparable
{
public override void Add(T v)
{
if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
else _root = SB_BinarySearchTree<T>.Insert(_root, v);
}
}
public class Set<T> where T : IComparable
{
protected SB_BinarySearchTree<T>.Node _root;
public T this[int idx] { get { return ElementAt(idx); } }
public long Count()
{
return SB_BinarySearchTree<T>.Count(_root);
}
public virtual void Add(T v)
{
if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
else
{
if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
_root = SB_BinarySearchTree<T>.Insert(_root, v);
}
}
public void Clear()
{
_root = null;
}
public void Remove(T v)
{
_root = SB_BinarySearchTree<T>.Remove(_root, v);
}
public bool Contains(T v)
{
return SB_BinarySearchTree<T>.Contains(_root, v);
}
public T ElementAt(long k)
{
var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
if (node == null) throw new IndexOutOfRangeException();
return node.Value;
}
public long Count(T v)
{
return SB_BinarySearchTree<T>.UpperBound(_root, v) - SB_BinarySearchTree<T>.LowerBound(_root, v);
}
public long LowerBound(T v)
{
return SB_BinarySearchTree<T>.LowerBound(_root, v);
}
public long UpperBound(T v)
{
return SB_BinarySearchTree<T>.UpperBound(_root, v);
}
public Tuple<long, long> EqualRange(T v)
{
if (!Contains(v)) return new Tuple<long, long>(-1, -1);
return new Tuple<long, long>(SB_BinarySearchTree<T>.LowerBound(_root, v), SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
}
public List<T> ToList()
{
return new List<T>(SB_BinarySearchTree<T>.Enumerate(_root));
}
}
public class SB_BinarySearchTree<T> where T : IComparable
{
public class Node
{
public T Value;
public Node LChild;
public Node RChild;
public long Count; //size of the sub tree
public Node(T v)
{
Value = v;
Count = 1;
}
}
static Random _rnd = new Random();
public static long 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, long 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, long 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, long 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 long UpperBound(Node t, T v)
{
var torg = t;
if (t == null) return 0;
var ret = long.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 == long.MaxValue ? Count(torg) : ret;
}
public static long LowerBound(Node t, T v)
{
var torg = t;
if (t == null) return 0;
var idx = Count(t) - Count(t.RChild) - 1;
var ret = long.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 == long.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, long 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);
}
}
#endregion
}