結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー nanophoto12
提出日時 2014-11-18 02:34:32
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 292 ms / 5,000 ms
コード長 1,115 bytes
コンパイル時間 732 ms
コンパイル使用メモリ 81,172 KB
実行使用メモリ 12,132 KB
最終ジャッジ日時 2025-01-02 17:03:39
合計ジャッジ時間 5,815 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <queue>

using namespace std;
typedef signed long long ll;

int pred(pair<int, ll> first, pair<int, ll> second)
{
	return first.second < second.second;
}

int main()
{
	ll n;
	cin >> n;
	vector<ll> bars(n);
	priority_queue<pair<double, int>> queue;
	for(int i = 0; i < n;i++)
	{
		cin >> bars[i];
		queue.push(make_pair(bars[i], i));
	}
	int q;
	cin >> q;
	vector<int> queries(q);
	for(int i = 0; i < q;i++)
	{
		cin >> queries[i];
	}
	
	const int maxValue = 500001;
	vector<int> taken(maxValue);
	vector<double> longest(maxValue);
	memset(&taken.front(), 0, sizeof(int)*maxValue);
	for(int i = 1; i < maxValue;i++)
	{
		double length = queue.top().first;
		longest[i] = length;
		int index = queue.top().second;
		queue.pop();
	    taken[index]++;
		queue.push(make_pair((double)bars[index] / (taken[index] + 1), index));
	}

	for(int m = 0;m < q;m++)
	{
		printf("%.15f\n", longest[queries[m]]);
	}
}
0