結果

問題 No.205 マージして辞書順最小
コンテスト
ユーザー bpyamasinn1
提出日時 2017-01-19 17:32:16
言語 C#(csc)
(csc 3.9.0)
結果
RE  
実行時間 -
コード長 2,975 bytes
コンパイル時間 1,005 ms
コンパイル使用メモリ 114,904 KB
実行使用メモリ 26,476 KB
最終ジャッジ日時 2024-12-23 01:31:03
合計ジャッジ時間 2,482 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other RE * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
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