結果
問題 | No.1534 おなかがいたい |
ユーザー | chikara-miki |
提出日時 | 2022-02-12 21:23:34 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 60 ms / 2,000 ms |
コード長 | 35,491 bytes |
コンパイル時間 | 7,236 ms |
コンパイル使用メモリ | 167,912 KB |
実行使用メモリ | 191,400 KB |
最終ジャッジ日時 | 2024-06-29 00:20:58 |
合計ジャッジ時間 | 9,246 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 48 ms
29,824 KB |
testcase_01 | AC | 52 ms
29,824 KB |
testcase_02 | AC | 44 ms
28,928 KB |
testcase_03 | AC | 52 ms
29,952 KB |
testcase_04 | AC | 52 ms
29,824 KB |
testcase_05 | AC | 51 ms
29,944 KB |
testcase_06 | AC | 44 ms
28,928 KB |
testcase_07 | AC | 52 ms
30,080 KB |
testcase_08 | AC | 54 ms
32,128 KB |
testcase_09 | AC | 52 ms
31,224 KB |
testcase_10 | AC | 43 ms
29,056 KB |
testcase_11 | AC | 51 ms
29,824 KB |
testcase_12 | AC | 52 ms
32,256 KB |
testcase_13 | AC | 44 ms
30,208 KB |
testcase_14 | AC | 43 ms
30,464 KB |
testcase_15 | AC | 53 ms
32,500 KB |
testcase_16 | AC | 58 ms
32,476 KB |
testcase_17 | AC | 60 ms
32,604 KB |
testcase_18 | AC | 60 ms
32,640 KB |
testcase_19 | AC | 58 ms
32,504 KB |
testcase_20 | AC | 58 ms
33,536 KB |
testcase_21 | AC | 51 ms
29,824 KB |
testcase_22 | AC | 51 ms
191,400 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (84 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 System.Collections.Generic; using System.IO; using System.Linq; using System.Numerics; using System.Text; using System.Text.RegularExpressions; using System.Xml.Xsl; using System.Reflection; using System.Diagnostics; using System.Collections; namespace Atcoder { public class Program { static void Main(string[] args) { var S = GetString(); if(!S.Contains("pain")) { Console.WriteLine(-1); return; } S = Regex.Replace(S, "pain.*", ""); S = Regex.Replace(S, "pon", "@"); var cnt = 0; for (int i = 0; i < S.Length; i++) { if (S[i] == '@') { cnt++; } } if(cnt < 2) { Console.WriteLine(-1); } else { Console.WriteLine(cnt - 1); } } public class CID { //OrderBy シーケンスの要素をキーに従って昇順に並べ替えます。 //OrderByDescending シーケンスの要素をキーに従って降順に並べ替えます。 //ThenBy キーに従って昇順のシーケンス内の要素の後続の並べ替えを実行します。 //ThenByDescending キーに従って降順に並べ替え、シーケンス内の要素の後続の並べ替えを実行します。 public CID(int l, int r) { L = l; R = r; } public int L { get; set; } public int R { get; set; } } #region よく使う定数 public static long INF = 1000000007; public static string FILLVALUE = "000000"; //上→右→下→左 public static int[] dx = new int[] { 0, 1, 0, -1 }; public static int[] dy = new int[] { -1, 0, 1, 0 }; #endregion #region 良く使う関数 /// <summary> /// 文字で埋める /// </summary> /// <param name="val">値</param> /// <returns></returns> static string Fill(long val) { return $"{val:FILLVALUE}"; } /// <summary> /// ファイル出力 /// </summary> /// <param name="path">出力先</param> /// <param name="append">false:上書き true:追加</param> /// <param name="text">内容</param> static void OutputFile(bool append, string text) { var path = "C:\\Users\\cmiki\\Desktop\\output.txt"; using (StreamWriter writer = new StreamWriter(path, append)) { writer.WriteLine(text); } } /// <summary> /// ファイルから取得 /// </summary> /// <param name="path">ファイルパス</param> /// <returns></returns> static List<List<int>> InputFile(string path) { var ret = new List<List<int>>(); StreamReader sr = new StreamReader(path); string line = null; while ((line = sr.ReadLine()) != null) { ret.Add(line.Split(' ').Select(i => int.Parse(i)).ToList()); } if (sr != null) { sr.Close(); } return ret; } /// <summary> /// 値から全パターン出力(何回使ってもOK) /// </summary> /// <param name="val">今の値</param> /// <param name="item">ベースのリスト</param> /// <param name="ans">戻すリスト</param> /// <param name="len">何桁までやるか</param> /// <returns></returns> static List<string> AllPattern(string val, List<char> items, List<string> ans, long N) { if (val.Length == N) { ans.Add(val); return ans; } foreach (var item in items) { AllPattern(val + item, items, ans, N); } return ans; } /// <summary> /// 値から全パターン出力(1回のみ) /// </summary> /// <param name="val">今の値</param> /// <param name="item">ベースのリスト</param> /// <param name="ans">戻すリスト</param> /// <param name="len">何桁までやるか</param> /// <param name="con">使ったかのフラグ</param> /// <returns></returns> static SortedSet<string> NoCoverPattern(string val, List<string> items, SortedSet<string> ans, int len, List<bool> con) { // 桁数に応じて変える if (val.Length == len) { ans.Add(val); return ans; } for (int i = 0; i < items.Count; i++) { if (con[i]) { con[i] = false; NoCoverPattern(val + items[i], items, ans, len, con); con[i] = true; } } return ans; } #endregion #region 値取得 #region string static string GetString() { return Console.ReadLine(); } static string[] GetStringArray() { return Console.ReadLine().Split(' ').ToArray(); } static List<string> GetStringList() { return Console.ReadLine().Split(' ').ToList(); } static List<string> GetStringRepeat(string val, int cnt) { return Enumerable.Repeat(val, cnt).ToList(); } static string[,] GetStringArrayHW(int H, int W) { var ret = new string[H, W]; for (int i = 0; i < H; i++) { var tmp = GetStringArray(); for (int j = 0; j < W; j++) { ret[i, j] = tmp[j]; } } return ret; } #endregion #region int static int GetInt() { return int.Parse(Console.ReadLine()); } static int[] GetIntArray() { return Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray(); } static List<int> GetIntList() { return Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToList(); } static List<int> GetIntRepeat(int val, int cnt) { return Enumerable.Repeat(val, cnt).ToList(); } static List<List<int>> GetIntListList(int N) { var ret = new List<List<int>>(); for (int i = 0; i < N; i++) { var tmp = GetIntList(); ret.Add(tmp); } return ret; } static int[,] GetIntArrayHW(int H, int W) { var ret = new int[H, W]; for (int i = 0; i < H; i++) { var tmp = GetIntArray(); for (int j = 0; j < W; j++) { ret[i, j] = tmp[j]; } } return ret; } #endregion #region BigIntger static BigInteger GetBigInt() { return BigInteger.Parse(Console.ReadLine()); } static BigInteger[] GetBigIntArray() { return Console.ReadLine().Split(' ').Select(i => BigInteger.Parse(i)).ToArray(); } #endregion #region long static long GetLong() { return long.Parse(Console.ReadLine()); } static long[] GetLongArray() { return Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray(); } static List<long> GetLongList() { return Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToList(); } static List<long> GetLongRepeat(long val, int cnt) { return Enumerable.Repeat(val, cnt).ToList(); } static List<List<long>> GetLongListList(long N) { var ret = new List<List<long>>(); for (long i = 0; i < N; i++) { var tmp = GetLongList(); ret.Add(tmp); } return ret; } static long[,] GetLongArrayHW(long H, long W) { var ret = new long[H, W]; for (long i = 0; i < H; i++) { var tmp = GetLongArray(); for (int j = 0; j < W; j++) { ret[i, j] = tmp[j]; } } return ret; } #endregion #region double static double GetDouble() { return double.Parse(Console.ReadLine()); } static double[] GetDoubleArray() { return Console.ReadLine().Split(' ').Select(i => double.Parse(i)).ToArray(); } static List<double> GetDoubleList() { return Console.ReadLine().Split(' ').Select(i => double.Parse(i)).ToList(); } static List<double> GetDoubleRepeat(double val, int cnt) { return Enumerable.Repeat(val, cnt).ToList(); } #endregion #region decimal static decimal GetDecimal() { return decimal.Parse(Console.ReadLine()); } static decimal[] GetDecimalArray() { return Console.ReadLine().Split(' ').Select(i => decimal.Parse(i)).ToArray(); } static List<decimal> GetDecimalList() { return Console.ReadLine().Split(' ').Select(i => decimal.Parse(i)).ToList(); } static List<decimal> GetDecimalRepeat(decimal val, int cnt) { return Enumerable.Repeat(val, cnt).ToList(); } #endregion #region bool static List<bool> GetBoolRepeat(bool val, int cnt) { return Enumerable.Repeat(val, cnt).ToList(); } static List<List<bool>> GetBoolRepeatHW(bool val, int H, int W) { var ret = new List<List<bool>>(); for (int i = 0; i < H; i++) { var tmp = Enumerable.Repeat(val, W).ToList(); ret.Add(tmp); } return ret; } #endregion #endregion #region 公式等 /// <summary> /// 左辺と右辺のルートを外して整数で比較 /// </summary> /// <param name="a">左辺1</param> /// <param name="b">左辺2</param> /// <param name="c">右辺</param> /// <returns>右辺が大きい:true</returns> public static bool RemoveRoot(long a,long b,long c) { /* √a +√b < √c (1) (√a +√b)^2 < c (2) 2√ab < c − a − b (3) c − a − b > 0 ∧ 4ab < (c − a − b)^2 */ var d = c - a - b; return 0 < d && 4 * a * b < d * d; } /// <summary> /// 串刺し問題は区間スケジューリング法 /// 右側で並び替えの右とって左を見る。 /// </summary> public static void Skewers() { //この形 var ND = GetIntArray(); var N = ND[0]; var D = ND[1]; var LR = new List<CID>(); for (int i = 0; i < N; i++) { var tmp = GetIntArray(); var t = new CID(tmp[0], tmp[1]); LR.Add(t); } LR = LR.OrderBy(x => x.R).ThenBy(x => x.L).ToList(); var cnt = 1; var min = LR[0].R; for (int i = 1; i < N; i++) { if (LR[i].L <= min + D - 1) { continue; } min = LR[i].R; cnt++; } Console.WriteLine(cnt); } /// <summary> /// 逆元 /// </summary> /// <param name="a"></param> /// <returns></returns> public static long Inverse(long a) { return modpow(a, INF - 2); } /// <summary> /// 本当の繰返二乗法 /// </summary> /// <param name="a">選択肢が何通り有るか</param> /// <param name="n">何個有るか</param> /// <param name="mod"></param> /// <returns></returns> public static long modpow(long a, long n) { a %= INF; long res = 1; while (n > 0) { if ((n & 1) == 1) res = (res * a) % INF; a = (a * a) % INF; n >>= 1; } return res; } /// <summary> /// 指定進数から10進数に戻す /// </summary> /// <param name="val">元の値</param> /// <param name="Num">変換元の進数(10進数以下)</param> /// <returns></returns> static long ChangDecimalnumber(long val, long Num) { long ans = 0; var cnt = 0; while (val != 0) { ans += ((val % 10) * (long)Math.Pow(Num, cnt)); val /= 10; cnt++; } return ans; } /// <summary> /// 10進数から指定進数に変換 /// </summary> /// <param name="val">元の値</param> /// <param name="Num">変換先の進数(10進数以下)</param> /// <returns></returns> static BigInteger ChangBaseNumber(BigInteger val, long Num) { if (val == 0) return 0; var li = new List<BigInteger>(); while (0 != val) { li.Add(val % Num); val /= Num; } li.Reverse(); return BigInteger.Parse(string.Join("", li)); } /// <summary> /// エラトステネスの篩 /// </summary> /// <param name="val">範囲の最大値</param> /// <returns>true:素数 false:素数ではない</returns> static List<bool> EratosthenesSieve(int val) { var dp = GetBoolRepeat(true, val + 1); dp[0] = dp[1] = false; var sq = (int)Math.Sqrt(val); for (int i = 2; i <= sq; i++) { if (dp[i]) { int n = i + i; while (n <= val) { dp[n] = false; n += i; } } } return dp; } /// <summary> /// 各桁の和 /// </summary> /// <param name="sum">合計</param> /// <param name="val">値</param> /// <returns></returns> static long DigitSum(long sum, long val) { sum += val % 10; val /= 10; if (val == 0) return sum; else return DigitSum(sum, val); } /// <summary> /// 自然数の和 /// </summary> /// <param name="num">最大数</param> /// <returns>合計</returns> static long Sumofnatural(long num) { return num * (num + 1) / 2; } /// <summary> /// 文字入れ替え /// </summary> /// <typeparam name="T"></typeparam> /// <param name="t1"></param> /// <param name="t2"></param> /// Swap(ref s[i2][p1 - N], ref s[i2][p2 - N]);の形式で呼出 static void Swap<T>(ref T t1, ref T t2) { T t3 = t1; t1 = t2; t2 = t3; } /// <summary> /// 回文チェック /// </summary> /// <param name="Target">文字列</param> /// <param name="len">文字数</param> /// <returns>true:回文 false:回文ではない</returns> static bool PalindromeCheck(string Target) { var len = Target.Length; for (int i = 0; i < len / 2; i++) { if (Target[i] != Target[len - 1 - i]) { return (false); } } return true; } /// <summary> /// アナグラムチェック 文字列の文字の構成が同じか(文字を入れ替えた時に同一になるか) /// </summary> /// <param name="word1"></param> /// <param name="word2"></param> /// <returns>true:アナグラム false:アナグラムではない</returns> static bool AnagramCheck(string word1, string word2) { char[] val1 = word1.ToCharArray(); char[] val2 = word2.ToCharArray(); Array.Sort(val1); Array.Sort(val2); word1 = new string(val1); word2 = new string(val2); return word1 == word2; //return word1.OrderBy(x => x).SequenceEqual(word2.OrderBy(x => x)); } /// <summary> /// 最小公倍数 /// </summary> /// <param name="a"></param> /// <param name="b"></param> /// <returns>最小公倍数</returns> public static long Lcm(long a, long b) { return a * b / Gcd(a, b); } /// <summary> /// 最大公約数 /// </summary> /// <param name="a"></param> /// <param name="b"></param> /// <returns>最大公約数</returns> public static long Gcd(long a, long b) { if (a < b) // 引数を入替えて自分を呼び出す return Gcd(b, a); while (b != 0) { var remainder = a % b; a = b; b = remainder; } return a; } /// <summary> /// 余弦定理 三角形の2辺とその接点の角度から残りの辺の長さを出す。 /// </summary> /// <param name="A">辺の長さ</param> /// <param name="B">辺の長さ</param> /// <param name="k">角度</param> /// <returns>辺の長さ</returns> public static double CosineTheorem(double A, double B, double k) { return Math.Sqrt(A * A + B * B - 2 * A * B * Math.Cos(Math.PI * k / 180)); } /// <summary> /// 正弦定理 外接円の半径と辺に対する角度から辺の長さを出す。※三角形 /// </summary> /// <param name="R">円の半径</param> /// <param name="k">角度</param> /// <returns>辺の長さ</returns> public static double SineTheorem(double R, double k) { return 2 * R * Math.Sin(k); } /// <summary> /// ユークリッド距離 /// </summary> /// <param name="x1">現在のx座標</param> /// <param name="y1">現在のy座標</param> /// <param name="x2">移動後のx座標</param> /// <param name="y2">移動後のy座標</param> /// <returns></returns> public static double EuclideanDistance(double x1, double y1, double x2, double y2) { return Math.Sqrt(Math.Pow(x1 - x2, 2) + Math.Pow(y1 - y2, 2)); } /// <summary> /// 繰返二乗法っぽいやつ /// </summary> /// <param name="val">値</param> /// <param name="div">割値</param> /// <param name="minus">引値</param> /// <returns></returns> public static long RepeatedSquares(long val, long div, long minus) { if (val == 1) return val; if (val % div == 0) { RepeatedSquares(val / div, div, minus); } else { RepeatedSquares(val - minus, div, minus); } return val; } /// <summary> /// 二分探索 /// </summary> /// <param name="items">検索リスト</param> /// <param name="target">検索対象</param> /// <returns>自分以下_最大indexを返す</returns> public static int BinarySearchNear(List<int> items, int target) { var min = 0; var max = items.Count; if (items[max - 1] < target) return max - 1; if (target < items[0]) return - 1; while (min + 1 < max) { var mid = (min + max) / 2; if (items[mid] <= target) min = mid; else max = mid; } return min; } /// <summary> /// 二分探索 /// </summary> /// <param name="items"></param> /// <param name="target"></param> /// <returns>自分以上_最小indexを返す</returns> public static int LowerBound(List<long> items, long target) { var min = -1; var max = items.Count; if (items[max - 1] < target) return max; if (target < items[0]) return 0; while (min + 1 < max) { var mid = (min + max) / 2; if (target <= items[mid]) max = mid; else min = mid; } return max; } /// <summary> /// 3点の座標に囲まれた三角形の面積 /// </summary> /// <param name="x1"></param> /// <param name="y1"></param> /// <param name="x2"></param> /// <param name="y2"></param> /// <param name="x3"></param> /// <param name="y3"></param> /// <returns></returns> public static bool TriangleArea(double x1, double y1, double x2, double y2, double x3, double y3) { //var result = 0d; var ln1 = LineLen(x1, y1, x2, y2); var ln2 = LineLen(x2, y2, x3, y3); var ln3 = LineLen(x3, y3, x1, y1); var tmp = new List<double>(); tmp.Add(ln1); tmp.Add(ln2); tmp.Add(ln3); tmp.Sort(); if (tmp[0] + tmp[1] <= tmp[2]) return false; else return true; //ヘロンの公式 //s=(a+b+c)/2 //S=√s(s-a)(s-b)(s-c) //var s1 = (ln1 + ln2 + ln3) / 2d; //var s2 = s1 * (s1 - ln1) * (s1 - ln2) * (s1 - ln3); //result = Math.Sqrt(s2); //return result; } /// <summary> /// 2点間の距離を返す /// </summary> /// <param name="x1"></param> /// <param name="y1"></param> /// <param name="x2"></param> /// <param name="y2"></param> /// <returns></returns> public static double LineLen(double x1, double y1, double x2, double y2) { return Math.Sqrt(Math.Pow(Math.Abs(x1 - x2), 2.0f) + Math.Pow(Math.Abs(y1 - y2), 2.0f)); } /// <summary> /// 組合せの数(順序違いは数えない) /// </summary> /// <param name="n">何個中</param> /// <param name="r">何個選ぶか</param> /// <returns></returns> public static Mint nCr(long n, long r) { var ret = new Mint(1); for (long i = n - r + 1; i <= n; i++) ret *= i; for (int i = 2; i <= r; i++) ret /= i; return ret; } /// <summary> /// 組合せの数(順序違いも数える) /// </summary> /// <param name="n">何個中</param> /// <param name="r">何個選ぶか</param> /// <returns></returns> public static Mint nPr(long n, long r) { var ret = new Mint(1); for (long i = n - r + 1; i <= n; i++) ret *= i; return ret; } #endregion #region クラス #region ユニオンファインド public class UnionFind { // 親要素のインデックスを保持する // 親要素が存在しない(自身がルートである)とき、マイナスでグループの要素数を持つ public int[] Parents { get; set; } public UnionFind(int n) { this.Parents = new int[n]; for (int i = 0; i < n; i++) { // 初期状態ではそれぞれが別のグループ(ルートは自分自身) // ルートなのでマイナスで要素数(1個)を保持する this.Parents[i] = -1; } } // 要素xのルート要素はどれか public int Find(int x) { // 親がマイナスの場合は自分自身がルート if (this.Parents[x] < 0) return x; // ルートが見つかるまで再帰的に探す // 見つかったルートにつなぎかえる this.Parents[x] = Find(this.Parents[x]); return this.Parents[x]; } // 要素xの属するグループの要素数を取得する public int Size(int x) { // ルート要素を取得して、サイズを取得して返す return -this.Parents[this.Find(x)]; } // 要素x, yが同じグループかどうか判定する public bool Same(int x, int y) { return this.Find(x) == this.Find(y); } // 要素x, yが属するグループを同じグループにまとめる public bool Union(int x, int y) { // x, y のルート x = this.Find(x); y = this.Find(y); // すでに同じグループの場合処理しない if (x == y) return false; // 要素数が少ないグループを多いほうに書き換えたい if (this.Size(x) < this.Size(y)) { var tmp = x; x = y; y = tmp; } // まとめる先のグループの要素数を更新 this.Parents[x] += this.Parents[y]; // まとめられるグループのルートの親を書き換え this.Parents[y] = x; return true; } } #endregion #region プライオリティキュー public class PriorityQueue<T> : IEnumerable<T> { private readonly List<T> _data = new List<T>(); private readonly IComparer<T> _comparer; private readonly bool _isDescending; public PriorityQueue(IComparer<T> comparer, bool isDescending = true) { _comparer = comparer; _isDescending = isDescending; } public PriorityQueue(Comparison<T> comparison, bool isDescending = true) : this(Comparer<T>.Create(comparison), isDescending) { } public PriorityQueue(bool isDescending = true) : this(Comparer<T>.Default, isDescending) { } public void Enqueue(T item) { _data.Add(item); var childIndex = _data.Count - 1; while (childIndex > 0) { var parentIndex = (childIndex - 1) / 2; if (Compare(_data[childIndex], _data[parentIndex]) >= 0) break; Swap(childIndex, parentIndex); childIndex = parentIndex; } } public T Dequeue() { var lastIndex = _data.Count - 1; var firstItem = _data[0]; _data[0] = _data[lastIndex]; _data.RemoveAt(lastIndex--); var parentIndex = 0; while (true) { var childIndex = parentIndex * 2 + 1; if (childIndex > lastIndex) break; var rightChild = childIndex + 1; if (rightChild <= lastIndex && Compare(_data[rightChild], _data[childIndex]) < 0) childIndex = rightChild; if (Compare(_data[parentIndex], _data[childIndex]) <= 0) break; Swap(parentIndex, childIndex); parentIndex = childIndex; } return firstItem; } public T Peek() { return _data[0]; } private void Swap(int a, int b) { var tmp = _data[a]; _data[a] = _data[b]; _data[b] = tmp; } private int Compare(T a, T b) { return _isDescending ? _comparer.Compare(b, a) : _comparer.Compare(a, b); } public int Count => _data.Count; public IEnumerator<T> GetEnumerator() { return _data.GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); } public class PriorityQueue<TKey, TValue> : IEnumerable<TValue> { private readonly List<KeyValuePair<TKey, TValue>> _data = new List<KeyValuePair<TKey, TValue>>(); private readonly bool _isDescending; private readonly Func<TValue, TKey> _keySelector; private readonly IComparer<TKey> _keyComparer; public PriorityQueue(Func<TValue, TKey> keySelector, bool isDescending = true) : this(keySelector, Comparer<TKey>.Default, isDescending) { } public PriorityQueue(Func<TValue, TKey> keySelector, IComparer<TKey> keyComparer, bool isDescending = true) { _keySelector = keySelector; _keyComparer = keyComparer; _isDescending = isDescending; } public void Enqueue(TValue item) { _data.Add(new KeyValuePair<TKey, TValue>(_keySelector(item), item)); var childIndex = _data.Count - 1; while (childIndex > 0) { var parentIndex = (childIndex - 1) / 2; if (Compare(_data[childIndex].Key, _data[parentIndex].Key) >= 0) break; Swap(childIndex, parentIndex); childIndex = parentIndex; } } public TValue Dequeue() { var lastIndex = _data.Count - 1; var firstItem = _data[0]; _data[0] = _data[lastIndex]; _data.RemoveAt(lastIndex--); var parentIndex = 0; while (true) { var childIndex = parentIndex * 2 + 1; if (childIndex > lastIndex) break; var rightChild = childIndex + 1; if (rightChild <= lastIndex && Compare(_data[rightChild].Key, _data[childIndex].Key) < 0) childIndex = rightChild; if (Compare(_data[parentIndex].Key, _data[childIndex].Key) <= 0) break; Swap(parentIndex, childIndex); parentIndex = childIndex; } return firstItem.Value; } public TValue Peek() { return _data[0].Value; } private void Swap(int a, int b) { var tmp = _data[a]; _data[a] = _data[b]; _data[b] = tmp; } private int Compare(TKey a, TKey b) { return _isDescending ? _keyComparer.Compare(b, a) : _keyComparer.Compare(a, b); } public int Count => _data.Count; public IEnumerator<TValue> GetEnumerator() { return _data.Select(r => r.Value).GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); } #endregion #region 特殊系 /// <summary> /// mod p の世界 /// </summary> public class Mint { public long x; public Mint(long x = 0) { this.x = ((x % INF + INF) % INF); } public static Mint operator -(Mint m, Mint n) { return new Mint((m.x + INF - n.x) % INF); } public static Mint operator -(Mint m, long n) { return new Mint((m.x + INF - (n % INF)) % INF); } public static Mint operator -(long m, Mint n) { return new Mint(((m % INF) + INF - n.x) % INF); } public static Mint operator +(Mint m, Mint n) { return new Mint((m.x + n.x) % INF); } public static Mint operator +(Mint m, long n) { return new Mint((m.x + (n % INF)) % INF); } public static Mint operator +(long m, Mint n) { return new Mint(((m % INF) + n.x) % INF); } public static Mint operator *(Mint m, Mint n) { return new Mint((m.x * n.x) % INF); } public static Mint operator *(Mint m, long n) { return new Mint((m.x * (n % INF)) % INF); } public static Mint operator *(long m, Mint n) { return new Mint(((m % INF) * n.x) % INF); } public static Mint operator /(Mint m, Mint n) { return new Mint((m.x * Inverse(n.x)) % INF); } public static Mint operator /(Mint m, long n) { return new Mint((m.x * Inverse((n % INF))) % INF); } public static Mint operator /(long m, Mint n) { return new Mint(((m % INF) * Inverse(n.x)) % INF); } } #endregion #endregion } }