結果
| 問題 |
No.649 ここでちょっとQK！
|
| コンテスト | |
| ユーザー |
👑  b1agmpo1e
|
| 提出日時 | 2025-11-18 19:25:17 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 806 ms / 3,000 ms |
| コード長 | 42,286 bytes |
| コンパイル時間 | 8,691 ms |
| コンパイル使用メモリ | 170,308 KB |
| 実行使用メモリ | 202,636 KB |
| 最終ジャッジ日時 | 2025-11-18 19:25:49 |
| 合計ジャッジ時間 | 31,188 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 32 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (146 ミリ秒)。 /home/judge/data/code/Main.cs(657,20): warning CS8981: 型名 'input' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(724,20): warning CS8981: 型名 'mod' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(64,23): warning CS8981: 型名 'node' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(747,20): warning CS8981: 型名 'toolbox' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/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/
ソースコード
namespace test
{
internal class Program
{
static void Main(string[] args)
{
cin = new input();
mod = new mod(998244353);
toolbox = new toolbox();
Priority_Queue = new Priority_Queue(true);
var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(sw);
toolbox.StartTimer();
int q=cin.intreed();
int k=cin.intreed();
var Query=new List<(int qtype,long val)>();
var set=new HashSet<long>();
while(q-->0)
{
int mode=cin.intreed();
if(mode==1)
{
var val=cin.longreed();
Query.Add((1,val));
set.Add(val);
}
else
{
Query.Add((2,-1));
}
}
var comp=new Compress<long>(set);
var tree=new BinaryTrie32();
foreach(var i in Query)
{
if(i.qtype==1)
{
tree.Insert(comp.raw2key[i.val]);
}
else if(tree.Size >= k)
{
var val=tree[k];//これは圧縮されてる
System.Console.WriteLine(comp[val]);
tree.Erase(val);
}
else
System.Console.WriteLine(-1);
}
toolbox.PrintElapsedTime();
Console.Out.Flush();
}
static input cin;
static mod mod;
static toolbox toolbox;
static Priority_Queue Priority_Queue;
}
public class ImplicitTreap
{
//1-indexです!!!!!!
private class node
{
public long val;//これは中身だよ 二分木のとしてのキーではない
public long QueryVal;//クエリ用の値 区間最小とか総和とか
public long lazy_val;//遅延伝搬用の値
public bool lazy_flg;//遅延するものがあるのか
public node left;//小さい
public node right;//大きい
public int cnt;//部分木の大きさ
public int priority;//優先度
public bool rev;// 反転フラグ
public node(long val, int priority, node left = null, node right = null)
{
this.val = val;
this.priority = priority;
this.left = left;
this.right = right;
}
public long update()
{
//部分木の大きさを最新にする
cnt = 1;
if (left != null) cnt += left.cnt;
if (right != null) cnt += right.cnt;
return cnt;
}
//ここはやりたいことによって変える
public void update_QueryVal()
{
//子から情報を吸い上げて親を最新の状態にする
QueryVal = val;
if (left != null) QueryVal += left.QueryVal;
if (right != null) QueryVal += right.QueryVal;
}
//これもやりたいことによって変える
public void Evaluate()
{
//自分自身に遅延評価を適用し、子はQueryValだけ更新し、それ以上の更新は子がEvaluateされた時にする
if (lazy_flg)
{
if (left != null)
{
left.QueryVal = lazy_val * left.cnt;
left.lazy_val = lazy_val;
left.lazy_flg = true;
}
if (right != null)
{
right.QueryVal = lazy_val * right.cnt;
right.lazy_val = lazy_val;
right.lazy_flg = true;
}
val = lazy_val;
lazy_val = 0;
lazy_flg = false;
}
if (rev)
{
// 子を左右反転
var tmp = left; left = right; right = tmp;
// 子に反転フラグを伝播（XOR）
if (left != null) left.rev = !left.rev;
if (right != null) right.rev = !right.rev;
rev = false;
}
//自分を最新にする
update_me();
}
public void update_me()
{
update();
update_QueryVal();
}
}
private node root;
private Random rand;
public ImplicitTreap(int seed = 998244353)
{
root = null;
rand = new Random(seed);
}
//内部向け
//indexがkey未満のノードとkey以上のノードに分割する
private void Split(node t, int key, out node left, out node right)
{
if (t == null)
{
left = null;
right = null;
return;
}
t.Evaluate();
int implicit_key = (t.left != null ? t.left.cnt : 0) + 1;
if (key <= implicit_key)
{
//key以上なので、今回のノードと右側部分木は右に行く
Split(t.left, key, out left, out t.left);
right = t;
}
else
{
//key未満なので、今回のノードと右側部分木は右に行く
Split(t.right, key - implicit_key, out t.right, out right);
left = t;
}
t.update_me();
}
//左と右を合体した新たな木(t)を作る
private void Marge(ref node t, node left, node right)
{
if (left != null) left.Evaluate();
if (right != null) right.Evaluate();
if (left == null || right == null)
{
t = left ?? right;
}
else if (left.priority > right.priority)
{
//leftの方が優先度高い
Marge(ref left.right, left.right, right);
t = left;
}
else
{
//rightの方が優先度高い
Marge(ref right.left, left, right.left);
t = right;
}
if (t != null) t.update_me();
}
//index=keyをitemに置き換える
private void Insert(ref node t, int key, node item)
{
Split(t, key, out node t1, out node t2);// t1: [0,key) t2:[key,n)
Marge(ref t1, t1, item);// t1: [0,key) + item
Marge(ref t, t1, t2);// t: [0,key) + item + [key,n)
}
private void Erase(ref node t, int key)
{
Split(t, key + 1, out node t1, out node t2);// t1: [0,key+1) t2:[key+1,n)
Split(t1, key, out t1, out node t3);// t1: [0,key) t3:[key,key+1)
Marge(ref t, t1, t2);// t: [0,key) + [key+1,n)
}
//index=keyの要素を取得
private long Get(node t, int k)
{
if (t == null || k < 1 || k > t.cnt)
throw new ArgumentOutOfRangeException(nameof(k));
t.Evaluate();
int leftCount = t.left != null ? t.left.cnt : 0;
if (k <= leftCount)
{
return Get(t.left, k);
}
else if (k == leftCount + 1)
{
return t.val;
}
else
{
return Get(t.right, k - leftCount - 1);
}
}
// --- クエリ [l, r) を計算する ---
// 【内部ワーカー】木の根が変わる可能性があるので ref node で受けて、最後に必ず復元して t に戻す。
private long GetQueryVal(ref node t, int l, int r)
{
if (t == null || l >= r) return 0;
// root を (<l) と (>=l) に分割
Split(t, l, out var t1, out var t2);
// (>=l) を (<r-l) と (>=r-l) に分割 ⇒ 真ん中が [l, r)
Split(t2, r - l + 1, out var t3, out var t4);
long ans = t3?.QueryVal ?? 0;
// 復元（順番厳守）
node back = null;
Marge(ref back, t3, t4); // back = (>=l)
Marge(ref t, t1, back); // t を元に戻す
return ans;
}
// 【ラッパ】node を受け取り、呼び出し側の木構造は変えない版。
// 参照をローカル変数に受けて ref でワーカーを呼ぶことで、見かけ上は非破壊になる。
private long GetQueryVal(node x, int l, int r)
{
return GetQueryVal(ref x, l, r);
}
// [l, r)に作用
private void RangeUpdate(ref node t, int l, int r, long val)
{
if (t == null || l >= r) return;
// ① (< l) と (>= l) に分割
Split(t, l, out var A, out var BR);
// ② (>= l) を、ちょうど (r-l) 個取り出すために (r-l+1) で分割
Split(BR, r - l + 1, out var B, out var C); // B が [l, r)
// ③ B 全体に「代入」Lazyを載せる
if (B != null)
{
B.lazy_flg = true;
B.lazy_val = val;
}
// ④ 復元（順序厳守）
node back = null;
Marge(ref back, B, C); // back = (>= l)
Marge(ref t, A, back); // t を元に戻す
}
// [l, r) を反転（1-index）
private void RangeReverse(ref node t, int l, int r)
{
if (t == null || l >= r) return;
// (<l) と (>=l) に分割
Split(t, l, out var A, out var BR);
// (>=l) から [l,r) を切り出す（r-l+1 に注意）
Split(BR, r - l + 1, out var B, out var C);
// 真ん中に反転lazyを立てる
if (B != null) B.rev = !B.rev;
// 復元
node back = null;
Marge(ref back, B, C);
Marge(ref t, A, back);
}
// [l, r) の先頭を m にするよう左回転（std::rotate と同義）
// 事前条件: l <= m <= r, 半開区間
private void Rotate(ref node t, int l, int m, int r)
{
if (t == null || l >= r || m == l || m == r) return; // 何もしないケースを早期終了
// reverse 3回
RangeReverse(ref t, l, r);
RangeReverse(ref t, l, l + (r - m));
RangeReverse(ref t, l + (r - m), r);
}
//外部向け
//indexにvalをぶっこむ 操作前のindex"以上"の要素は右にずれる 例:[1,2,3]にInsert(2,100) => [1,100,2,3]
public void Insert(int index, long val) => Insert(ref root, index, new node(val, rand.Next()));
public void Erase(int index) => Erase(ref root, index);
//末尾に追加
public void PushBack(long val) => Insert(Count() + 1, val);
public int Count() => root?.cnt ?? 0;
public long this[int index] => Get(root, index);
//[l,r)のモノイド積を取得
public long GetQueryVal(int l, int r)
{
return GetQueryVal(ref root, l, r);
}
//[l,r]に作用
public void RangeUpdate(int l, int r, long val) => RangeUpdate(ref root, l, r, val);
//[l,r)を反転
public void RangeReverse(int l, int r) => RangeReverse(ref root, l, r);
//[l,r)をn回左に順回シフト
public void RangeRotateLeft(int l, int r, int n)
{
if (l >= r) return;
int len = r - l;
int k = ((n % len) + len) % len; // 0..len-1 に正規化
if (k == 0) return;
int m = l + k; // 先頭が m になるように
Rotate(ref root, l, m, r);
}
public void test()
{
for (int i = 1; i <= 10; ++i) PushBack(i);
RangeRotateLeft(1, 6, 2);
for (int i = 1; i <= Count(); ++i)
Console.WriteLine(Get(root, i));
}
public List<long> dump()
{
var back = new List<long>();
dump(root, back);
return back;
}
private void dump(node t, List<long> back)
{
if (t == null) return;
t.Evaluate();
dump(t.left, back);
back.Add(t.val);
dump(t.right, back);
}
}
public class Compress<T>
where T : struct, IComparable
{
//1indexだよ!!!! 例[1,5,8,9,5,5]=>[1,2,3,4,2,2]
public Dictionary<int, T> key2raw;
public Dictionary<T, int> raw2key;
//やりたいこと 構築 生=>圧縮後 圧縮後=>生
public Compress(IEnumerable<T> vector = null)
{
key2raw = new Dictionary<int, T>();
raw2key = new Dictionary<T, int>();
if (vector is { })
Build(vector);
}
public List<int> Build(IEnumerable<T> vector)
{
int cnt = 0;
var back = new List<int>();
foreach (var i in vector.OrderBy(i => i))
{
if (!raw2key.ContainsKey(i))
{
cnt++;
raw2key.Add(i, cnt);
key2raw.Add(cnt, i);
}
}
foreach (var i in vector)
back.Add(raw2key[i]);
return back;
}
//インデクサは圧縮後=>生
public T this[int k] => key2raw[k];
public int Count => key2raw.Count;
}
/// <summary>
/// 非負整数の集合を管理し、
/// 挿入・削除・最小/最大要素取得・k番目取得・XOR最小値取得・
/// 値の型は int（32ビット）に固定しています。
/// </summary>
public class BinaryTrie32
{
private const int B = 21; // int は32ビット
private class Node
{
public int Count; // 部分木に含まれる要素数
public Node Left; // ビット0枝
public Node Right; // ビット1枝
public Node()
{
Count = 0;
Left = null;
Right = null;
}
}
private Node root = null;
// ————————————————
// 挿入／削除（点更新）
// ————————————————
private Node Add(Node t, int val, int b)
{
if (t == null) t = new Node();
t.Count++;
if (b < 0) return t;
int bit = (val >> b) & 1;
if (bit == 0)
t.Left = Add(t.Left, val, b - 1);
else
t.Right = Add(t.Right, val, b - 1);
return t;
}
private Node Sub(Node t, int val, int b)
{
if (t == null) return null;
t.Count--;
if (t.Count == 0) return null;
if (b < 0) return t;
int bit = (val >> b) & 1;
if (bit == 0)
t.Left = Sub(t.Left, val, b - 1);
else
t.Right = Sub(t.Right, val, b - 1);
return t;
}
// ————————————————
// XOR最小値／最大値取得
// ————————————————
private int GetMin(Node t, int val, int b)
{
if (t == null) throw new InvalidOperationException("Trie is empty");
if (b < 0) return 0;
int f = (val >> b) & 1;
Node targetChild = (f == 0) ? t.Left : t.Right;
if (targetChild == null)
{
f = 1 - f;
targetChild = (f == 0) ? t.Left : t.Right;
}
int res = GetMin(targetChild, val, b - 1);
return res | (f << b);
}
// ————————————————
// k番目小さい要素取得
// ————————————————
private int Get(Node t, int k, int b)
{
if (t == null || k < 1 || k > t.Count)
throw new ArgumentOutOfRangeException(nameof(k));
int result = 0;
while (b >= 0 && t != null)
{
int leftCount = t.Left != null ? t.Left.Count : 0;
if (k <= leftCount)
{
t = t.Left;
}
else
{
result |= (1 << b);
t = t.Right;
k -= leftCount;
}
b--;
}
return result;
}
// ————————————————
// lower_bound／upper_bound の内部：要素 < val の個数を数える
// ————————————————
private int CountLower(Node t, int val, int b)
{
if (t == null || b < 0) return 0;
int bit = (val >> b) & 1;
int cnt = (bit == 1 && t.Left != null) ? t.Left.Count : 0;
Node targetChild = (bit == 0) ? t.Left : t.Right;
return cnt + CountLower(targetChild, val, b - 1);
}
// ————————————————
// public API
// ————————————————
/// <summary>集合の要素数を返す。</summary>
public int Size => root != null ? root.Count : 0;
/// <summary>空かどうかを返す。</summary>
public bool IsEmpty => root == null;
/// <summary>x を集合に追加する。</summary>
public void Insert(int x) => root = Add(root, x, B - 1);
/// <summary>x を集合から削除する（存在しない場合は何もしない）。</summary>
public void Erase(int x) => root = Sub(root, x, B - 1);
/// <summary>x XOR v が最小となる v を返す。</summary>
public int MinXor(int x) => GetMin(root, x, B - 1);
/// <summary>x XOR v が最大となる v を返す。</summary>
public int MaxXor(int x) => GetMin(root, ~x, B - 1);
/// <summary>集合内の最小要素を返す。</summary>
public int MinElement() => MinXor(0);
/// <summary>集合内の最大要素を返す。</summary>
public int MaxElement() => MaxXor(0);
/// <summary>
/// lower_bound(x)：
/// 集合内で値 x 以上の最小の要素の「番号」を取得します。
/// ここで「番号」とは小さい方から何番目か（1-indexed）を指します。
/// ⇒ 内部的には要素 ＜ x の個数 + 1を返します。
/// つまり、集合の最大値より大きいvalを投げると、集合の要素数 + 1が返ってくる
/// </summary>
public int LowerBound(int val) => CountLower(root, val, B - 1) + 1;
/// <summary>
/// upper_bound(x)：
/// 集合内で値 x より大きい最小の要素の「番号」を取得します。
/// ここで「番号」とは小さい方から何番目か（1-indexed）を指します。
/// ⇒ 内部的には要素 ≤ x の個数 + 1を返します（val+1 を lower_bound しているため）。
/// つまり、集合の最大値以上のvalを投げると、集合の要素数 + 1が返ってくる
/// </summary>
public int UpperBound(int val) => CountLower(root, val + 1, B - 1) + 1;
/// <summary>k 番目（1-indexed）に小さい要素を返す。</summary>
public int this[int k] => Get(root, k, B - 1);
/// <summary>要素 val の集合内での個数を返す。</summary>
public int Count(int val)
{
Node t = root;
for (int i = B - 1; i >= 0 && t != null; i--)
{
int bit = (val >> i) & 1;
t = (bit == 0) ? t.Left : t.Right;
}
return t != null ? t.Count : 0;
}
}
public static class Extensions
{
public static Dictionary<T, int> safe_addtion_for_dictionary_int<T>(this Dictionary<T, int> dic, T key)
{
if (dic.ContainsKey(key))
dic[key]++;
else
dic.Add(key, 1);
return dic;
}
public static Dictionary<T, long> safe_addtion_for_dictionary_long<T>(this Dictionary<T, long> dic, T key)
{
if (dic.ContainsKey(key))
dic[key]++;
else
dic.Add(key, 1);
return dic;
}
public static Dictionary<T, List<T2>> safe_addtion_for_list_in_dictionary<T, T2>(this Dictionary<T, List<T2>> dic, T key, T2 value)
{
if (dic.ContainsKey(key))
dic[key].Add(value);
else
dic.Add(key, new List<T2>() { value });
return dic;
}
public static T list_pop_back<T>(this List<T> a)
{
var k = a[a.Count - 1];
a.RemoveAt(a.Count - 1);
return k;
}
public static T chmin<T>(ref this T a, T b)
where T : struct, IComparable
{
if (a.CompareTo(b) > 0)
return a = b;
else
return a;
}
public static T chmax<T>(ref this T a, T b)
where T : struct, IComparable
{
if (a.CompareTo(b) < 0)
return a = b;
else
return a;
}
}
internal class input
{
string[] soloinput;
int t;
public input()
{
soloinput = new string[0];
t = 0;
}
public string soloreed()
{
if (t < soloinput.Length)
{
return soloinput[t++];
}
string input = Console.ReadLine();
while (input == "")
{
input = Console.ReadLine();
}
soloinput = input.Split(" ");
t = 0;
return soloinput[t++];
}
public int intreed()
{
return int.Parse(soloreed());
}
public int[] arrayint(int N)
{
int[] A = new int[N];
for (int i = 0; i < N; i++)
{
A[i] = intreed();
}
return A;
}
public long longreed()
{
return long.Parse(soloreed());
}
public long[] arraylong(long N)
{
long[] A = new long[N];
for (long i = 0; i < N; i++)
{
A[i] = longreed();
}
return A;
}
public decimal decimalreed()
{
return decimal.Parse(soloreed());
}
public decimal[] arraydecimal(long N)
{
decimal[] A = new decimal[N];
for (decimal i = 0; i < N; i++)
{
A[(long)i] = decimalreed();
}
return A;
}
}
internal class mod
{
public long T { get; set; }
public mod(long mod = 1000000007)
{
T = mod;
}
public long addition(long A, long B)
{
long C = A + B;
return (long)C % T;
}
public long subtraction(long A, long B)
{
return ((A % T) - (B % T) + T) % T;
}
public long multiplication(long A, long B)
{
return ((A % T) * (B % T)) % T;
}
}
internal class toolbox
{
string Y = "Yes";
string N = "No";
static input cin;
private DateTime? startTime;
public toolbox()
{
cin = new input();
}
public long[] CumulativeSum(long[] A, bool mode = true)
{
if (mode == false) Array.Reverse(A);
long[] back = new long[A.Length + 1];
back[0] = 0;
for (int i = 1; i <= A.Length; i++)
{
back[i] = back[i - 1] + A[i - 1];
}
if (mode == false) Array.Reverse(A);
return back;
}
public long[] Eratosthenes(long A)
{
A++;
var back = new List<long>();
bool[] ch = new bool[A];
for (int i = 2; i < A; i++) ch[i] = true;
for (long i = 2; i < Math.Sqrt(A); i++)
{
if (ch[i] == true)
{
back.Add(i);
for (long t = 1; i * t < A; t++)
{
ch[i * t] = false;
}
}
}
for (long i = 0; i < A; i++)
{
if (ch[i] == true) back.Add(i);
}
return back.Distinct().ToArray();
}
public void Swap<T>(ref T a, ref T b)
{
var i = a;
a = b;
b = i;
}
public void LSwap<T>(ref List<T> A, int a, int b)
{
var i = A[a];
A[a] = A[b];
A[b] = i;
}
public long Gcd(long A, long B)
{
while (A != 0)
{
B %= A;
Swap(ref A, ref B);
}
return B;
}
public long[] AllDivisors(long N)
{
var back = new List<long>();
for (int i = 1; Math.Pow(i, 2) <= N; i++)
{
if (N % i == 0)
{
back.Add(i);
back.Add(N / i);
}
}
return back.Distinct().ToArray();
}
public static IEnumerable<T[]> ExhaustiveEnumeration<T>(IEnumerable<T> indata)
{
if (indata.Count() == 1) yield return new T[] { indata.First() };
foreach (var i in indata)
{
var used = new T[] { i };
var unused = indata.Except(used);
foreach (var t in ExhaustiveEnumeration(unused))
yield return used.Concat(t).ToArray();
}
//How to use
//var allpattern = toolbox.ExhaustiveEnumeration(Enumerable.Range(1, N));
}
public bool[,] bitallsearch(int N)
{
bool[,] back = new bool[(int)Math.Pow(2, N), N];
for (int i = 0; i < Math.Pow(2, N); i++)
{
for (int t = 0; t < N; t++)
{
var k = (i >> t) & 1;
if (k == 1)
{
back[i, t] = true;
}
}
}
return back;
}
public static int BS<T>(T[] A, T key)
where T : IComparable
{
//このコード、定数倍が大変な事になってるので標準ライブラリを使いましょう(BinarySearch)
int left = 0;
int right = A.Length;
int mid = 0;
while (left < right)
{
mid = (left + right) / 2;
if (A[mid].CompareTo(key) == 0)
return mid;
else if (A[mid].CompareTo(key) > 0)
right = mid;
else if (A[mid].CompareTo(key) < 0)
left = mid + 1;
}
return -1;
}
public static int lower_bound<T>(T[] a, T v)
{
return lower_bound(a, v, Comparer<T>.Default);
}
public static int lower_bound<T>(T[] A, T key, Comparer<T> v)
{
int left = 0;
int right = A.Length - 1;
int mid = 0;
var W = 0;
while (left <= right)
{
mid = (left + right) / 2;
W = v.Compare(A[mid], key);
if (W == -1)
left = mid + 1;
else
right = mid - 1;
}
return left;
}
public long[] prime_factorize(long N)
{
long T = N;
var back = new List<long>();
for (long i = 2; i * i <= T; i++)
{
if (T % i != 0) continue;
while (T % i == 0)
{
back.Add(i);
T /= i;
}
}
if (T != 1) back.Add(T);
return back.ToArray();
}
public long[] One_dimensional_Coordinate_Compression(long[] A)
{
long[] back = new long[A.Length];
var T = A.Distinct().ToList();
T.Sort();
for (int i = 0; i < A.Length; i++)
back[i] = T.BinarySearch(A[i]);
return back;
}
public void setYN(string A = "Yes", string B = "No")
{
Y = A;
N = B;
}
public void YN(bool ans)
{
if (ans)
Console.WriteLine(Y);
else
Console.WriteLine(N);
}
public string[] x_dekakou(int H, int W)
{
var s = new string[H + 2];
for (int i = 0; i < W + 2; i++)
{
s[0] += "x";
s[H + 1] += "x";
}
for (int i = 1; i < H + 1; i++)
{
//x場外 .白 #黒
s[i] = "x" + Console.ReadLine().Replace(" ", "") + "x";
}
return s;
}
public List<List<char>> x_dekakou_char(int H, int W)
{
var grid = new List<List<char>>(H + 2);
var border = new List<char>(W + 2);
for (int i = 0; i < W + 2; i++)
border.Add('x');
grid.Add(new List<char>(border));
for (int i = 0; i < H; i++)
{
var line = Console.ReadLine()?.Replace(" ", "") ?? string.Empty;
var row = new List<char>(W + 2);
row.Add('x');
foreach (var c in line)
row.Add(c);
row.Add('x');
grid.Add(row);
}
grid.Add(new List<char>(border));
return grid;
}
public List<List<int>> x_dekakou_string(int H, int W)
{
var back = new List<List<int>>();
for (int i = 0; i < H + 2; i++)
back.Add(Enumerable.Repeat<int>(-1, W + 2).ToList());
for (int i = 0; i < W + 2; i++)
{
back[0][i] = -1;
back[H + 1][i] = -1;
}
for (int i = 1; i <= H; i++)
{
back[i][0] = -1;
back[i][W + 1] = -1;
for (int t = 1; t <= W; t++)
back[i][t] = cin.intreed();
}
return back;
}
/// <summary>
/// 配列の指定位置以降を反転する
/// </summary>
/// <param name="array">反転対象の配列</param>
/// <param name="begin">反転開始位置（この位置以降が反転される）</param>
private void Reverse<T>(T[] array, int begin) where T : IComparable<T>
{
// 反転する要素が2個未満の場合は何もしない
if (array.Length - begin < 2) return;
// 両端から中央に向かって要素を交換
int left = begin;
int right = array.Length - 1;
while (left < right)
{
Swap(ref array[left], ref array[right]);
left++;
right--;
}
}
/// <summary>
/// 配列を辞書順で次の順列に変更する
/// 全ての順列を列挙するには、事前に Array.Sort() でソートした配列を渡すこと
/// </summary>
/// <param name="array">順列を生成する配列（事前ソート必須）</param>
/// <returns>次の順列が存在する場合true、最大順列の場合false</returns>
public bool NextPermutation<T>(T[] array) where T : IComparable<T>
{
// 辞書順で次に大きい順列を生成
// 1. 右端から降順でない位置を探す
int pivotIndex = -1;
for (int i = array.Length - 2; i >= 0; i--)
{
if (array[i].CompareTo(array[i + 1]) < 0) // 昇順ペア発見
{
pivotIndex = i;
break;
}
}
// 最大順列に到達している場合
if (pivotIndex == -1) return false;
// 2. pivotより大きい最右の要素と交換
for (int j = array.Length - 1; j > pivotIndex; j--)
{
if (array[pivotIndex].CompareTo(array[j]) < 0)
{
Swap(ref array[pivotIndex], ref array[j]);
break;
}
}
// 3. pivot以降を昇順に並べ直し
Reverse(array, pivotIndex + 1);
return true;
// how to use
// do{}while(NextPermutation)
}
/// <summary>
/// 回文判定のコア処理（配列版）
/// </summary>
private bool IsPalindromeCore<T>(T[] array, int left, int right) where T : IComparable<T>
{
while (left < right)
{
if (array[left].CompareTo(array[right]) != 0)
return false;
left++;
right--;
}
return true;
}
/// <summary>
/// 回文判定のコア処理（文字列版）
/// </summary>
private bool IsPalindromeCore(string str, int left, int right)
{
while (left < right)
{
if (str[left] != str[right])
return false;
left++;
right--;
}
return true;
}
/// <summary>
/// 配列全体が回文かどうかを判定
/// </summary>
public bool IsPalindrome<T>(T[] array) where T : IComparable<T>
{
return IsPalindromeCore(array, 0, array.Length - 1);
}
/// <summary>
/// 文字列全体が回文かどうかを判定
/// </summary>
public bool IsPalindrome(string str)
{
return IsPalindromeCore(str, 0, str.Length - 1);
}
/// <summary>
/// 指定範囲が回文かどうかを判定（配列版）
/// </summary>
public bool IsPalindrome<T>(T[] array, int start, int end) where T : IComparable<T>
{
return IsPalindromeCore(array, start, end);
}
/// <summary>
/// 指定範囲が回文かどうかを判定（文字列版）
/// </summary>
public bool IsPalindrome(string str, int start, int end)
{
return IsPalindromeCore(str, start, end);
}
/// <summary>
/// 指定長さの部分配列に回文が含まれるかを判定
/// </summary>
public bool HasPalindrome<T>(T[] array, int length) where T : IComparable<T>
{
for (int i = 0; i <= array.Length - length; i++)
{
if (IsPalindromeCore(array, i, i + length - 1))
return true;
}
return false;
}
/// <summary>
/// 指定長さの部分文字列に回文が含まれるかを判定
/// </summary>
public bool HasPalindrome(string str, int length)
{
for (int i = 0; i <= str.Length - length; i++)
{
if (IsPalindromeCore(str, i, i + length - 1))
return true;
}
return false;
}
public long modpow(long x, long p, long mod = 1000000007)
{
long result = 1;
x %= mod;
while (p > 0)
{
if (p % 2 == 1) // pが奇数の場合
{
result = (result * x) % mod;
}
x = (x * x) % mod; // xを二乗（これが繰り返し二乗）
p /= 2; // pを半分にする
}
return result;
}
public void StartTimer()
{
startTime = DateTime.Now;
}
public void PrintElapsedTime(bool error_output = true)
{
//標準出力ではなくて標準エラー出力を使ってるのでatcoderのジャッジはこの出力を無視する つまり消さなくてok 便利だね
if (startTime.HasValue)
{
var elapsed = DateTime.Now - startTime.Value;
if (error_output)
Console.Error.WriteLine($"Elapsed time: {elapsed.TotalMilliseconds} ms");
else
Console.WriteLine($"Elapsed time: {elapsed.TotalMilliseconds} ms");
}
else
{
Console.Error.WriteLine("Timer was not started.");
}
}
}
internal class Priority_Queue
{
toolbox toolbox = new toolbox();
public List<(long, long)> Queue { get; private set; }
/// <summary>
/// true==>大きいやつから出るよ false==>小さいやつからでるよ
/// </summary>
public bool revase { get; set; }
public Priority_Queue(bool cnt = true)
{
Queue = new List<(long, long)>();
revase = cnt;
}
public void Enqueue(long a, long b)
{
if (revase == false)
a *= -1;
int i = Queue.Count, t;
Queue.Add((a, b));
while (i != 0)
{
t = (i - 1) / 2;
if (Queue[i].Item1 > Queue[t].Item1)
{
var k = Queue[i];
Queue[i] = Queue[t];
Queue[t] = k;
i = t;
}
else
{
break;
}
}
}
public (long, long) Dequeue()
{
int a = Queue.Count - 1;
var back = Queue[0];
Queue[0] = Queue[a];
Queue.RemoveAt(a);
for (int i = 0, j; (j = 2 * i + 1) < a;)
{
if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)
j++;
if (Queue[i].Item1 < Queue[j].Item1)
{
var k = Queue[i];
Queue[i] = Queue[j];
Queue[j] = k;
i = j;
}
else
{
break;
}
}
if (revase == false)
back.Item1 *= -1;
return back;
}
public (long, long) GetPeek() => (revase ? Queue[0].Item1 : Queue[0].Item1 * -1, Queue[0].Item2);
}
internal class Generic_Priority_Queue<T>
{
toolbox toolbox = new toolbox();
public List<(long, T)> Queue { get; private set; }
/// <summary>
/// true==>大きいやつから出るよ false==>小さいやつからでるよ
/// </summary>
public bool revase { get; set; }
public Generic_Priority_Queue(bool cnt = true)
{
Queue = new List<(long, T)>();
revase = cnt;
}
public void Enqueue(long a, T b)
{
if (revase == false)
a *= -1;
int i = Queue.Count, t;
Queue.Add((a, b));
while (i != 0)
{
t = (i - 1) / 2;
if (Queue[i].Item1 > Queue[t].Item1)
{
var k = Queue[i];
Queue[i] = Queue[t];
Queue[t] = k;
i = t;
}
else
{
break;
}
}
}
public (long, T) Dequeue()
{
int a = Queue.Count - 1;
var back = Queue[0];
Queue[0] = Queue[a];
Queue.RemoveAt(a);
for (int i = 0, j; (j = 2 * i + 1) < a;)
{
if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)
j++;
if (Queue[i].Item1 < Queue[j].Item1)
{
var k = Queue[i];
Queue[i] = Queue[j];
Queue[j] = k;
i = j;
}
else
{
break;
}
}
if (revase == false)
back.Item1 *= -1;
return back;
}
public (long, T) get_first()
{
if (Queue.Count == 0)
return (default(long), default(T));
else
return Queue[0];
}
}
}