結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー EmKjpEmKjp
提出日時 2015-03-22 11:27:32
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 288 ms / 5,000 ms
コード長 3,775 bytes
コンパイル時間 664 ms
コンパイル使用メモリ 88,436 KB
実行使用メモリ 17,392 KB
最終ジャッジ日時 2023-09-11 09:20:50
合計ジャッジ時間 11,358 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 287 ms
17,272 KB
testcase_01 AC 288 ms
17,220 KB
testcase_02 AC 287 ms
17,320 KB
testcase_03 AC 263 ms
17,216 KB
testcase_04 AC 261 ms
17,288 KB
testcase_05 AC 265 ms
17,392 KB
testcase_06 AC 281 ms
17,024 KB
testcase_07 AC 285 ms
16,940 KB
testcase_08 AC 251 ms
16,700 KB
testcase_09 AC 258 ms
16,864 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<functional>
#include<complex>

using namespace std;
#define BET(a,b,c) ((a)<=(b)&&(b)<(c))
#define FOR(i,n) for(int i=0,i##_end=(int(n));i<i##_end;i++)
#define SZ(x) (int)(x.size())
#define ALL(x) (x).begin(),(x).end()
#define MP make_pair
#define FOR_EACH(it,v) for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++)
typedef vector<int> VI;
typedef vector<VI> VVI;

int L[100000];
int K[100000];

typedef long long ll_t;

ll_t gcd(ll_t s,ll_t t) { return t ? gcd(t , s%t) : max(s,-s); }
ll_t lcm(ll_t s,ll_t t) { return s/gcd(s,t)*t; }
struct rational{
    mutable ll_t a,b;
    rational(ll_t aa=0,ll_t bb=1) : a(aa),b(bb){
        if(b<0) {
            a = -a ;  b = -b ;
        }
        reduce();
    }
    rational(string s){
        if(s.find('/')==string::npos){
            istringstream in(s);
            in>>a; b=1;
        }else{
            s[s.find('/')]=' ';
            istringstream in(s);
            in>>a>>b; if(b==0) abort();
        }
        if(b<0) {
            a = -a ;  b = -b ;
        }
        reduce();
    }
    void reduce() const{
        if(a==0){
            b=1;
        }else{
            ll_t g = gcd(a,b);
            a/=g ; b/=g;
        }
    }
    double get_value() const {
        return 1.0 * a / b ; 
    }
    rational inverse(){
        return rational(b,a);
    }
    friend rational operator+(const rational &r1 , const rational&r2){
        ll_t l = lcm(r1.b,r2.b);
        ll_t v = r1.a * (l / r1.b) + r2.a * (l / r2.b) ;
        return rational(v , l);
    }
    friend rational operator-(const rational &r1 , const rational&r2){
        ll_t l = lcm(r1.b,r2.b);
        ll_t v = r1.a * (l / r1.b) - r2.a * (l / r2.b) ;
        return rational(v , l);
    }
    friend rational operator*(const rational &r1 , const rational&r2){
        return rational(r1.a*r2.a , r1.b*r2.b);
    }
    friend rational operator/(const rational &r1 , const rational&r2){
        return rational(r1.a*r2.b , r1.b*r2.a);
    }
    rational operator + () {
        return rational(a,b) ; 
    }
    rational operator - () {
        return rational(-a,b);
    }
    friend long long compare(const rational &r1 , const rational&r2) {
        return r1.a*r2.b-r2.a*r1.b;
    }

#define DEF_OP(op)                                  \
    rational& operator op##= (const rational &r)    \
    { return *this = (*this) op r ; }
    DEF_OP(+) DEF_OP(-)  DEF_OP(*) DEF_OP(/)
#undef DEF_OP

#define DEF_COMP(op)                                                    \
    friend bool operator op (const rational& r1 , const rational& r2)   \
    { return compare(r1,r2) op 0 ; }                                      

    DEF_COMP(==) DEF_COMP(!=) DEF_COMP(>=) DEF_COMP(<=) DEF_COMP(>) DEF_COMP(<) 
#undef DEF_COMP

    friend ostream& operator<<(ostream& o , rational r){
        if(r.b==1) return o << r.a ;
        return o << r.a << "/" << r.b ;
    }
};

double ans[5 * 100000 + 10];
vector<rational> events;
priority_queue<rational> qu;

int main()
{
    int N,Q;
    scanf("%d",&N);
    FOR(i,N) scanf("%d",&L[i]);
    scanf("%d",&Q);
    FOR(i,Q) scanf("%d",&K[i]);
    auto maxK = *max_element(K, K + Q);
    FOR(i,N) qu.push(L[i]);
    while(SZ(events) <= maxK){
        auto r = qu.top(); qu.pop();
        events.push_back(r);
        r.b++;
        qu.push(r);
    }
    FOR(i,maxK + 1){
        auto r = events[i];
        while(i < SZ(events) && r == events[i]){
            ans[++i] = r.get_value();
        }
        i--;
    }
    FOR(i,Q) printf("%.20f\n", ans[K[i]]);
    return 0;
}
0