結果

問題 No.68 よくある棒を切る問題 (2)
コンテスト
ユーザー kuuso1
提出日時 2014-11-17 01:06:22
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 2,036 ms / 5,000 ms
コード長 4,999 bytes
コンパイル時間 1,157 ms
コンパイル使用メモリ 116,472 KB
実行使用メモリ 53,660 KB
最終ジャッジ日時 2025-01-01 18:10:14
合計ジャッジ時間 29,709 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
raw source code 

using System;
using System.Collections;
using System.Collections.Generic;
 
class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		PriorityQueue<Pair> PQ=new PriorityQueue<Pair>();
		for(int i=0;i<N;i++){
			PQ.Push(new Pair(L[i],i));
		}
		
		int[] divide=new int[N];
		
		int cnt=0;
		double[] Ans=new double[500001];
		while(cnt<500000){
			Pair P=PQ.Top;PQ.Pop();
			cnt++;
			Ans[cnt]=P.len;
			divide[P.idx]++;
			PQ.Push(new Pair(P.len*(divide[P.idx])/(divide[P.idx]+1),P.idx));
		}
		
		for(int i=0;i<Q;i++){
			Console.WriteLine(Ans[K[i]]);
		}
	}
	int N;
	double[] L;
	int Q;
	int[] K;
	public Sol(){
		N=ri();
		L=rda();
		Q=ri();
		K=ria();
		
	}



	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(){return Console.ReadLine().Split(' ');}
	static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
	static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}
	static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));}
}
class Pair:IComparable<Pair>{
	public double len;
	public int idx;
	public Pair(double l_,int i_){
		len=l_;idx=i_;
	}
	public int CompareTo(Pair y){
		return this.len>y.len?1:this.len<y.len?-1:0;
	}
}

class PriorityQueue<T> where T:IComparable<T>{

	//T:IComparable
	//IComparerかComparisonを指定してインスタンス化する事も可
	//引数なしインスタンス化⇒ComparedToで比較
	//大きいものほどTopへ

	enum typeCompare{
		isIComparerable=1,
		useIComparer=2,
		useDComparison=3
	}

	List<T> buffer;
	typeCompare tComp;
	IComparer<T> Cmper;
	Comparison<T> Cmp;
	
	public PriorityQueue(IComparer<T> comparer_){
		this.buffer=new List<T>();
		tComp=typeCompare.useIComparer;
		Cmper=comparer_;
		Cmp=null;
	}
	public PriorityQueue(){
		this.buffer=new List<T>();
		tComp=typeCompare.isIComparerable;
	}
	public PriorityQueue(Comparison<T> cmp_){
		this.buffer=new List<T>();
		tComp=typeCompare.useDComparison;
		Cmp=cmp_;
		Cmper=null;
	}
	public PriorityQueue(int capacity,IComparer<T> comparer_){
		this.buffer=new List<T>(capacity);
		tComp=typeCompare.useIComparer;
		Cmper=comparer_;
	}
	public PriorityQueue(int capacity){
		this.buffer=new List<T>(capacity);
		tComp=typeCompare.isIComparerable;
	}
	public PriorityQueue(int capacity,Comparison<T> cmp_){
		this.buffer=new List<T>(capacity);
		tComp=typeCompare.useDComparison;
		Cmp=cmp_;
	}
	

	void PushHeap(List<T> arr,T elem){
		int n=arr.Count;
		buffer.Add(elem);
		
		if(tComp==typeCompare.isIComparerable){
			try{
			while(n!=0){
				int i=(n-1)/2;
				if(arr[n].CompareTo(arr[i]) > 0){
					T tmp=arr[n];arr[n]=arr[i];arr[i]=tmp;
				}
				n=i;
			}
			}
		        catch (Exception e){
				Console.WriteLine("{0} Exception caught.", e);
		        }
		}else if(tComp==typeCompare.useIComparer){
			try{
			while(n!=0){
				int i=(n-1)/2;
				if(Cmper.Compare(arr[n],arr[i]) > 0){
					T tmp=arr[n];arr[n]=arr[i];arr[i]=tmp;
				}
				n=i;
			}
			}
		        catch (Exception e){
				Console.WriteLine("{0} Exception caught.", e);
		        }
		}else if(tComp==typeCompare.useDComparison){
			while(n!=0){
				int i=(n-1)/2;
				if(Cmp(arr[n],arr[i]) > 0){
					T tmp=arr[n];arr[n]=arr[i];arr[i]=tmp;
				}
				n=i;
			}
		}
	}
	
	void PopHeap(List<T> arr){
		int n=arr.Count - 1;
		arr[0] = arr[n];
		arr.RemoveAt(n);
		
		if(tComp==typeCompare.isIComparerable){
			for (int i=0,j;(j = 2*i +1)<n;){
				if((j!=n - 1)&&(arr[j].CompareTo(arr[j+1])<0))j++;
				if (arr[i].CompareTo(arr[j])<0){
					T tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp;
				}
				i=j;
			}
      		}else if(tComp==typeCompare.useIComparer){
			for (int i=0,j;(j = 2*i +1)<n;){
				if((j!=n - 1)&&(Cmper.Compare(arr[j],arr[j+1])<0))j++;
				if (Cmper.Compare(arr[i],arr[j])<0){
					T tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp;
				}
				i=j;
			}
		}else if(tComp==typeCompare.useDComparison){
			for (int i=0,j;(j = 2*i +1)<n;){
				if((j!=n - 1)&&(Cmp(arr[i],arr[j])<0))j++;
				if (Cmp(arr[i],arr[j])<0){
					T tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp;
				}
				i=j;
			}
		}
	}
	
	
	
	public void Push(T elem){
		PushHeap(this.buffer, elem);
	}
	
	public void Pop(){
		PopHeap(this.buffer);
	}
	
	public bool Contains(T elem){
		return this.buffer.Contains(elem);
	}
	public T Top{
		get{return this.buffer[0];}
	}
	
	public int Count{
		get{return this.buffer.Count;}
	}
	
	public T this[int i]{
		get{return this.buffer[i];}
	}
	
	public bool IsEmpty{
		get{return this.buffer.Count==0;}
	}
}
0