QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#554231#8242. V-DiagramRafat_KabirAC ✓84ms5584kbC++203.1kb2024-09-09 08:58:102024-09-09 08:58:11

Judging History

你现在查看的是最新测评结果

  • [2024-09-09 08:58:11]
  • 评测
  • 测评结果:AC
  • 用时:84ms
  • 内存:5584kb
  • [2024-09-09 08:58:10]
  • 提交

answer

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <time.h>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>

using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>

using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// to erase in multiset-> less_equal<T> and 
// s.erase(s.find_by_order(s.order_of_key(x)))
// lower_bound(x)=>(cannot use the stl lower_bound function)
// ll idx = s.order_of_key(x)
// if(idx == s.size()) -> no lower_bound
// else lb = *s.find_by_order(idx) // as 0-indexing
// idx-1 will give highest value which is strictly less than x
// for upper_bound->do the same with (x+1)

typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef tuple<ll, ll, ll> t64;
typedef vector<t64> vt64;
typedef vector<vt64> vvt64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef vector<vector<p32> > vvp32;
typedef vector<bool> vb;
ll mod =  1e9+7, MOD = 998244353;
double eps = 1e-12;
// #define forn(i,e) for(ll i = 0; i < e; i++)
#define FOR(s, e, i) for(int i = s; i <= e; i++)
// #define rforn(i,s) for(ll i = s; i >= 0; i--)
#define ROF(s ,e, i) for(int i = s; i >= e; i--)
#define coutAll(A) for(auto asdafas : A) cout <<  asdafas << " "; cout << "\n";
#define foutAll(A) for(auto asdafas : A) fout <<  asdafas << " "; cout << "\n";
#define cinAll(A) for(auto &asdafas : A) cin >>  asdafas;
#define finAll(A) for(auto &asdafas : A) fin >>  asdafas;
#define minpq priority_queue<ll, v64, greater<ll>>
#define maxpq priority_queue<ll> 
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fi first
#define se second
ll inf = LLONG_MAX;
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> pii;
//#define MAXN 1000000

void solve(int it)
{
    ll n; cin >> n;
    v64 A(n); cinAll(A);
    ll id = min_element(all(A)) - A.begin();
    // cout << id << " ";
    auto f = [&](ll i, ll j)->ld{
        ld sum = 0;
        FOR(i, j, k) sum += A[k];
        return sum / (j-i+1);
    };
    cout << fixed << setprecision(20) <<
     max({f(0,n-1), f(id-1, n-1), f(0, id+1)}) << "\n";
}


int main()
{
    fast_cin();    
    ll t = 1;
    cin >> t;
    for(int it=1; it<=t; it++)
    {
        //cout << "Case " << it << ": ";
        solve(it);
    }
    return 0;
}


这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3720kb

input:

2
4
8 2 7 10
6
9 6 5 3 4 8

output:

6.75000000000000000000
5.83333333333333333348

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 84ms
memory: 3784kb

input:

100000
3
948511478 739365502 813471668
3
881046825 27458122 398507422
3
987554257 399092415 924260278
3
984128569 125199021 716360525
3
529589236 45783262 313507287
3
645443456 85994112 226010681
3
914820717 228360911 572267310
3
418958362 56703604 195276041
3
64461646 26764720 26995581
3
914535039 ...

output:

833782882.66666666668606922030
435670789.66666666665696538985
770302316.66666666668606922030
608562705.00000000000000000000
296293261.66666666665696538985
319149416.33333333334303461015
571816312.66666666668606922030
223646002.33333333332848269492
39407315.66666666666787932627
383253737.666666666656...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 27ms
memory: 3892kb

input:

10000
4
194123849 79274911 191162487 570110764
86
957917218 915359202 914726017 873273226 867724859 867674150 809652204 805531383 745262007 743835491 727071232 714782071 645394643 639432679 594879540 587173904 583418126 560538589 518721836 469558994 427721766 411582333 404948350 402948978 357228675 ...

output:

258668002.75000000000000000000
527118856.75555555554456077516
495489050.35294117647572420537
525232841.14999999999417923391
472025965.70000000001164153218
546154003.12500000000000000000
543366581.51612903224304318428
254833443.19999999999708961695
428466450.04999999998835846782
502458665.38461538462...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 16ms
memory: 3960kb

input:

1000
357
999039850 998470288 997001139 994662646 991895879 986310400 986201443 971759917 969292691 967648767 963962459 963603069 959189978 954532156 936459732 927268934 925199105 918559276 906725073 903024522 891346023 886340039 872105565 871168803 867996002 862017068 851751458 849013653 847967471 8...

output:

493655540.62745098039158619940
515292672.41666666665696538985
498032099.98148148148902691901
481127839.62500000000000000000
526924843.33628318583942018449
488725771.45719178082072176039
533287305.94642857142025604844
438471966.33333333334303461015
536630212.25757575756870210171
560617979.73972602741...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 15ms
memory: 3904kb

input:

100
1152
999672457 998726401 995956848 990786177 990411263 984766135 983346495 982593760 982250360 980153123 975942408 974567443 973232196 970303426 967381747 966555245 966400114 965308448 961378668 960953166 960451796 957742285 957273419 956986267 956737190 956352393 954265694 953272327 952096100 9...

output:

504372755.02915951973409391940
495156421.17748197447508573532
511090599.62176165802520699799
497554816.12431444242247380316
514036973.34556848701322451234
509664056.91205211725900880992
500937804.96366639141342602670
515638734.54323995127924717963
500934821.10958276019664481282
518390767.73920552677...

result:

ok 100 numbers

Test #6:

score: 0
Accepted
time: 16ms
memory: 4540kb

input:

10
29043
999960631 999958134 999901247 999737433 999520614 999519045 999460207 999379140 999279078 999214335 999048733 998866618 998693991 998649435 998636721 998575997 998542938 998513617 998477418 998422985 998403836 998262102 998124856 998017139 998013085 997959891 997944356 997893923 997524695 9...

output:

497704976.04656609491212293506
500149119.64892215983127243817
499456770.18277040091925300658
500288732.70241785491816699505
505548409.83238636364694684744
502546060.65180180181050673127
500560614.16313028967124409974
502706676.39949874687590636313
500677023.49624583945842459798
505195094.97029702970...

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 20ms
memory: 5584kb

input:

1
300000
999995409 999991717 999988340 999981078 999978323 999978096 999977575 999967796 999958049 999950023 999927083 999923421 999918905 999916153 999912740 999911175 999907902 999902376 999899096 999889548 999888902 999880881 999878324 999867494 999866296 999864006 999863565 999859765 999841183 9...

output:

499603654.39723860876983962953

result:

ok found '499603654.397238612', expected '499603654.397238612', error '0.000000000'

Extra Test:

score: 0
Extra Test Passed