Submission #316795
Source Code Expand
using System; using System.Collections.Generic; using System.Text; using sc = Scanner; using System.Collections; class Program { static void Main(string[] args) { int n = sc.NextInt(); int k = sc.NextInt(); PriorityQueue<int[]> ranking = new PriorityQueue<int[]>((a, b) => {return b[1]-a[1]; }); int[] answer = {0,0}; int[][] answerCollector = new int[n-k+1][]; int indexAC = 0; for (int i = 0; i < k; i++) { ranking.Push(new int[]{ i + 1, sc.NextInt() }); } answer = ranking.Pop(); answerCollector[indexAC] = (int[])answer.Clone(); indexAC++; for (int i = k; i < n; i++) { ranking.Push(new int[]{i+ 1,sc.NextInt()}); int[] tmp = ranking.Pop(); if (tmp[1] < answer[1])//次の候補者の方が若い { answer = tmp; } answerCollector[indexAC] = (int[])answer.Clone(); indexAC++; } for (int i = 0; i < answerCollector.Length; i++) { Console.WriteLine(answerCollector[i][0]); } } } /// <summary> /// ・一般的なデータ構造のオブジェクトT /// ・Icomparableを持った「新たなクラスを生成すること無く」比較方法の動的化 /// を目的とした優先度付きキュー,comparison にCompareToを入れる /// 1回あたりの計算量はPop PushともにO(logn) /// </summary> /// <typeparam name="T"></typeparam> class PriorityQueue<T> { ArrayList array; public int Count { get{return array.Count;}} Comparison<T> comparison; /// <summary> /// コンストラクタ /// </summary> /// <param name="comparison">Tに対する比較方向を示すデリゲート, (a,b)のとき返り値intに a_int - b_int (a > b) なら昇順,逆なら降順</param> public PriorityQueue(Comparison<T> comparison) { this.comparison = comparison; array = new ArrayList(); } /// <summary> /// ヒープ化されている配列リストに新しい要素を追加する。 /// </summary> /// <param name="array">対象の配列リスト</param> private void PushHeap(T elem) { int n = array.Count; array.Add(elem); while (n != 0) { int i = (n - 1) / 2; // 親と値を入れ替え if (comparison((T)array[n], (T)array[i]) < 0) { T tmp = (T)array[n]; array[n] = array[i]; array[i] = tmp; } n = i; } } /// <summary> /// ヒープから指定した値を削除する。 /// </summary> /// <param name="array">対象の配列リスト</param> private T PopHeap() { if (array.Count == 0) throw new IndexOutOfRangeException("要素が0のキューに要素を取り出す命令がおこなわれました"); int n = array.Count - 1; T returnItem = (T)array[0]; array[0] = array[n]; array.RemoveAt(n); for (int i = 0, j; (j = 2 * i + 1) < n; ) { // 値の大きい方の子を選ぶ if ((j != n - 1) && (comparison((T)array[j],(T)array[j+1]) > 0)) j++; // 子と値を入れ替え if (comparison((T)array[i], (T)array[j]) > 0) { T tmp = (T)array[j]; array[j] = array[i]; array[i] = tmp; } i = j; } return returnItem; } /// <summary> /// 要素のプッシュ. /// </summary> /// <param name="elem">挿入したい要素</param> public void Push(T elem) { PushHeap(elem); } /// <summary> /// 要素をポップ.出したデータはコレクションの中から消える /// </summary> /// <returns></returns> public T Pop() { return PopHeap(); } /// <summary> /// 要素を全て消去する /// </summary> public void Clear() { array.Clear(); } } public static class Scanner { public static string[] NextStrArray() { return Console.ReadLine().Split(' '); } public static long[] NextLongArray() { string[] s = NextStrArray(); long[] a = new long[s.Length]; for (int i = 0; i < a.Length; i++) { a[i] = long.Parse(s[i]); } return a; } public static int[] NextIntArray() { string[] s = NextStrArray(); int[] a = new int[s.Length]; for (int i = 0; i < a.Length; i++) { a[i] = int.Parse(s[i]); } return a; } public static int NextInt() { string tmp = ""; while (true) { string readData = char.ConvertFromUtf32(Console.Read()); if (readData == " " || readData == "\n") break; tmp += readData; } return int.Parse(tmp); } public static double NextDouble() { string tmp = ""; while (true) { string readData = char.ConvertFromUtf32(Console.Read()); if (readData == " " || readData == "\n") break; tmp += readData; } return double.Parse(tmp); } public static long NextLong() { string tmp = ""; while (true) { string readData = char.ConvertFromUtf32(Console.Read()); if (readData == " " || readData == "\n") break; tmp += readData; } return long.Parse(tmp); } public static double[] NextDoubleArray() { string[] s = NextStrArray(); double[] a = new double[s.Length]; for (int i = 0; i < a.Length; i++) { a[i] = double.Parse(s[i]); } return a; } }
Submission Info
Submission Time | |
---|---|
Task | B - 特別賞 |
User | pekoong |
Language | C# (Mono 2.10.8.1) |
Score | 100 |
Code Size | 6179 Byte |
Status | AC |
Exec Time | 1171 ms |
Memory | 15100 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 40 / 40 | 60 / 60 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
Subtask1 | sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt |
Subtask2 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 111 ms | 7332 KB |
sample_02.txt | AC | 106 ms | 7408 KB |
subtask1_01.txt | AC | 108 ms | 7400 KB |
subtask1_02.txt | AC | 109 ms | 7396 KB |
subtask1_03.txt | AC | 106 ms | 7404 KB |
subtask1_04.txt | AC | 111 ms | 7400 KB |
subtask1_05.txt | AC | 123 ms | 7556 KB |
subtask1_06.txt | AC | 115 ms | 7560 KB |
subtask1_07.txt | AC | 113 ms | 7464 KB |
subtask1_08.txt | AC | 117 ms | 7528 KB |
subtask1_09.txt | AC | 116 ms | 7532 KB |
subtask1_10.txt | AC | 117 ms | 7500 KB |
subtask1_11.txt | AC | 118 ms | 7520 KB |
subtask2_01.txt | AC | 281 ms | 8552 KB |
subtask2_02.txt | AC | 120 ms | 7536 KB |
subtask2_03.txt | AC | 1126 ms | 15100 KB |
subtask2_04.txt | AC | 843 ms | 14820 KB |
subtask2_05.txt | AC | 479 ms | 14448 KB |
subtask2_06.txt | AC | 1085 ms | 14700 KB |
subtask2_07.txt | AC | 1124 ms | 15032 KB |
subtask2_08.txt | AC | 1171 ms | 14832 KB |
subtask2_09.txt | AC | 1113 ms | 15084 KB |