結果

問題 No.205 マージして辞書順最小
ユーザー bpyamasinn1bpyamasinn1
提出日時 2017-01-19 17:32:16
言語 C#(csc)
(csc 3.9.0)
結果
RE  
実行時間 -
コード長 2,975 bytes
コンパイル時間 6,569 ms
コンパイル使用メモリ 105,048 KB
実行使用メモリ 24,832 KB
最終ジャッジ日時 2023-08-24 17:14:30
合計ジャッジ時間 6,451 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;

namespace test
{
	class MainClass
	{
		static void ReadStdin() { Console.SetIn(new System.IO.StreamReader("stdin.txt")); }

		public static void Main()
		{
			ReadStdin();
			var count = Int32.Parse(Console.ReadLine());
			//reversed_priority_queue<string> que;
			var que = new PriorityQueue<string>();
			for (int i = 0; i < count; i++)
			{
				var s = Console.ReadLine();
				s += '\xff';
				que.Push(s);
			}

			string ans = "";
			while (que.Count() != 0) {
				string t = que.Peek(); 
				que.Pop();
				ans += t[0];
				if (t.Length != 2)
				{ // 1 is for the sentinel
					que.Push(t.Substring(1));
				}
			}
			Console.WriteLine(ans);
		}
	}
	//template<class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

	public class PriorityQueue<T> where T : IComparable
	{
		private IComparer<T> _comparer = null;
		private int _type = 0;

		private T[] _heap;
		private int _sz = 0;

		private int _count = 0;

		/// <summary>
		/// Priority Queue with custom comparer
		/// </summary>
		public PriorityQueue(IComparer<T> comparer)
		{
			_heap = new T[128];
			_comparer = comparer;
		}

		/// <summary>
		/// Priority queue
		/// </summary>
		/// <param name="type">0: asc, 1:desc</param>
		public PriorityQueue(int type = 0)
		{
			_heap = new T[128];
			_type = type;
		}

		private int Compare(T x, T y)
		{
			if (_comparer != null) return _comparer.Compare(x, y);
			return _type == 0 ? x.CompareTo(y) : y.CompareTo(x);
		}

		public void Push(T x)
		{
			_count++;
			if (_count > _heap.Length)
			{
				var newheap = new T[_heap.Length * 2];
				for (int n = 0; n < _heap.Length; n++) newheap[n] = _heap[n];
				_heap = newheap;
			}

			//node number
			var i = _sz++;

			while (i > 0)
			{
				//parent node number
				var p = (i - 1) / 2;

				if (Compare(_heap[p], x) <= 0) break;

				_heap[i] = _heap[p];
				i = p;
			}

			_heap[i] = x;
		}

		public T Pop()
		{
			_count--;

			T ret = _heap[0];
			T x = _heap[--_sz];

			int i = 0;
			while (i * 2 + 1 < _sz)
			{
				//children
				int a = i * 2 + 1;
				int b = i * 2 + 2;

				if (b < _sz && Compare(_heap[b], _heap[a]) < 0) a = b;

				if (Compare(_heap[a], x) >= 0) break;

				_heap[i] = _heap[a];
				i = a;
			}

			_heap[i] = x;

			return ret;
		}

		public int Count()
		{
			return _count;
		}

		public T Peek()
		{
			return _heap[0];
		}

		public bool Contains(T x)
		{
			for (int i = 0; i < _sz; i++) if (x.Equals(_heap[i])) return true;
			return false;
		}

		public void Clear()
		{
			while (this.Count() > 0) this.Pop();
		}

		public IEnumerator<T> GetEnumerator()
		{
			var ret = new List<T>();

			while (this.Count() > 0)
			{
				ret.Add(this.Pop());
			}

			foreach (var r in ret)
			{
				this.Push(r);
				yield return r;
			}
		}

		public T[] ToArray()
		{
			T[] array = new T[_sz];
			int i = 0;

			foreach (var r in this)
			{
				array[i++] = r;
			}

			return array;
		}
	}
}
0