結果
問題 | No.68 よくある棒を切る問題 (2) |
ユーザー | t98slider |
提出日時 | 2022-05-19 10:57:29 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 285 ms / 5,000 ms |
コード長 | 2,973 bytes |
コンパイル時間 | 1,856 ms |
コンパイル使用メモリ | 180,452 KB |
実行使用メモリ | 7,472 KB |
最終ジャッジ日時 | 2024-09-17 16:34:41 |
合計ジャッジ時間 | 6,196 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 285 ms
7,388 KB |
testcase_01 | AC | 280 ms
7,260 KB |
testcase_02 | AC | 270 ms
7,472 KB |
testcase_03 | AC | 256 ms
7,256 KB |
testcase_04 | AC | 268 ms
7,384 KB |
testcase_05 | AC | 258 ms
7,392 KB |
testcase_06 | AC | 253 ms
6,940 KB |
testcase_07 | AC | 265 ms
7,180 KB |
testcase_08 | AC | 242 ms
6,940 KB |
testcase_09 | AC | 250 ms
6,996 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; struct yuri { ll num,den; yuri() : num(0),den(1) {} yuri(ll a) : num(a),den(1){} yuri(ll a,ll b) : num(a),den(b){safe();} void safe(){ //if(den<0)den*=-1,num*=-1; //ll v=__gcd(abs(num),den); //num/=v,den/=v; } yuri& operator++() {num+=den;return *this;} yuri& operator--() {num-=den;return *this;} yuri& operator+=(const yuri& rhs) { num=num*rhs.den+den*rhs.num; den=den*rhs.den; safe(); return *this; } yuri& operator-=(const yuri& rhs) { num=num*rhs.den-den*rhs.num; den=den*rhs.den; safe(); return *this; } yuri& operator*=(const yuri& rhs) { num=num*rhs.num; den=den*rhs.den; safe(); return *this; } yuri& operator/=(const yuri& rhs) { num=num*rhs.den; den=den*rhs.num; safe(); return *this ; } yuri operator+() const { return *this; } yuri operator-() const { return yuri() - *this; } friend yuri operator+(const yuri& lhs, const yuri& rhs) { return yuri(lhs) += rhs; } friend yuri operator-(const yuri& lhs, const yuri& rhs) { return yuri(lhs) -= rhs; } friend yuri operator*(const yuri& lhs, const yuri& rhs) { return yuri(lhs) *= rhs; } friend yuri operator/(const yuri& lhs, const yuri& rhs) { return yuri(lhs) /= rhs; } friend bool operator==(const yuri& lhs, const yuri& rhs) { return (lhs.num==rhs.num&&lhs.den==rhs.den); } friend bool operator!=(const yuri& lhs, const yuri& rhs) { return (lhs.num!=rhs.num||lhs.den!=rhs.den); } friend bool operator<(const yuri& lhs, const yuri& rhs) { return (lhs.num*rhs.den<lhs.den*rhs.num); } friend bool operator<=(const yuri& lhs, const yuri& rhs) { return (lhs.num*rhs.den<=lhs.den*rhs.num); } friend bool operator>(const yuri& lhs, const yuri& rhs) { return (lhs.num*rhs.den>lhs.den*rhs.num); } friend bool operator>=(const yuri& lhs, const yuri& rhs) { return (lhs.num*rhs.den>=lhs.den*rhs.num); } friend ostream& operator << (ostream &os, const yuri& rhs) noexcept { if(rhs.den==1)return os << rhs.num; return os << rhs.num << '/' << rhs.den; } }; int main(){ int n, q; cin >> n; vector<ll> l(n); priority_queue<yuri> pq; for(auto &&v: l){ cin >> v; pq.push(v); } cin >> q; vector<pair<int,int>> Q(q); vector<double> ans(q); for(int i = 0; i < q; i++){ cin >> Q[i].first; Q[i].second = i; } sort(Q.begin(), Q.end()); yuri p = 1ll << 60; for(int i = 0, j = 1, cnt = 0; i < q; i++){ while(cnt < Q[i].first){ auto q = pq.top(); p = min(p, pq.top()); q.den++; pq.pop(); pq.push(q); cnt++; } ans[Q[i].second] = double(p.num) / p.den; } for(int i = 0; i < q; i++){ printf("%.15lf\n",ans[i]); } }