QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#686313#9532. 长野原龙势流星群N_z_50 294ms166092kbC++237.8kb2024-10-29 11:05:372024-10-29 11:05:39

Judging History

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

  • [2024-10-29 11:05:39]
  • 评测
  • 测评结果:50
  • 用时:294ms
  • 内存:166092kb
  • [2024-10-29 11:05:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace Fread{const int SIZE=1<<16;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return *S++;}}namespace Fwrite{const int SIZE=1<<16;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{~NTR(){flush();}}ztr;}
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#define Setprecision 10
#define between '\n'
template<typename T>struct is_char{static constexpr bool value=(std::is_same<T,char>::value||std::is_same<T,signed char>::value||std::is_same<T,unsigned char>::value);};template<typename T>struct is_integral_ex{static constexpr bool value=(std::is_integral<T>::value||std::is_same<T,__int128>::value)&&!is_char<T>::value;};template<typename T>struct is_floating_point_ex{static constexpr bool value=std::is_floating_point<T>::value||std::is_same<T,__float128>::value;};namespace Fastio{struct Reader{template<typename T>typename std::enable_if_t<std::is_class<T>::value,Reader&>operator>>(T&x){for(auto &y:x)*this>>y;return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1;while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;return *this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1,s=0;x=0;T t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Reader&>operator>>(T&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}Reader&operator>>(std::string&str){str.clear();char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{typedef __int128 mxdouble;template<typename T>typename std::enable_if_t<std::is_class<T>::value,Writer&>operator<<(T x){for(auto &y:x)*this<<y<<between;*this<<'\n';return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Writer&>operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Writer&>operator<<(T x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(T)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x+0.5;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Writer&>operator<<(T c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(std::string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
constexpr int lim=50,up=1e9;
int fa[200001];
pair<long long,int>w[lim][200001];
vector<int>son[lim][200001];
int dfn[200001],dc=0,st[21][200001],ban[200001];
double ans[200001],dp[200001],l,r,mi;
void dfs0(int u,int f)
{
    st[0][dfn[u]=++dc]=f;
    for(auto v:son[0][u])
    dfs0(v,u);
}
int tmin(int u,int v)
{
    return dfn[u]<dfn[v]?u:v;
}
int lca(int u,int v)
{
    if(u==v)return u;
    u=dfn[u],v=dfn[v];
    if(u>v)swap(u,v);
    int k=__lg(v-u);
    return tmin(st[k][u+1],st[k][v-(1<<k)+1]);
}
void dfs(int round,int u)
{
    dp[u]=w[round][u].first-w[round][u].second*mi;
    for(auto v:son[round][u])
    {
        dfs(round,v);
        if(!ban[v]&&dp[v]>=0)dp[u]+=dp[v];
    }
}
int key[200001];
pair<long long,int>calcw1(int round,int u,int nban=0)
{
    // dbg(make_tuple(mi,round,u,ans[u],key[u],w[round-1][u]));
    w[round][u]=w[round-1][u];
	if(ban[u]&&ban[u]<round)nban=1;
	else if(nban)ban[u]=round;
	else ban[u]=0;
	if(key[u])nban=0;
    for(auto v:son[round-1][u])
    {
		int nxt=nban;
		if(ans[v]<l)nxt=1;
        auto _=calcw1(round,v,nxt);
        // dbg(make_tuple(u,v,_));
		if(!ban[v])
		{
			w[round][u].first+=_.first;
			w[round][u].second+=_.second;
		}
    }
    if(key[u])return {0,0};
    if(ans[u]>=mi)return w[round][u];
    else return {0,0};
}
pair<long long,int>calcw2(int round,int u,int nban=0)
{
    // dbg(make_tuple(mi,round,u,ans[u],key[u],w[round-1][u]));
    w[round][u]=w[round-1][u];
	if(ban[u]&&ban[u]<round)nban=1;
	else if(nban)ban[u]=round;
	else ban[u]=0;
	if(key[u])nban=0;
    for(auto v:son[round-1][u])
    {
		int nxt=nban;
		if(ans[v]<mi)nxt=1;
        auto _=calcw2(round,v,nxt);
        // dbg(make_tuple(u,v,_));
		if(!ban[v])
		{
			w[round][u].first+=_.first;
			w[round][u].second+=_.second;
		}
    }
    if(key[u])return {0,0};
    if(ans[u]>=r)return w[round][u];
    else return {0,0};
}
void solve(double l,double r,int round,const vector<int>&fvv)
{
    // dbg(make_tuple(l,r,round,fvv));
    // dbg(son[round],w[round],ban[round]);
	// assert(round<=lim);
	if((r-l)/l<=1e-6)return;
    if(fvv.empty())return;
    double mi=(l+r)/2;
    ::mi=mi,::l=l,::r=r;
    dfs(round,fvv[0]);
    // dbg(dp);
    vector<int>fvv1,fvv2;
    for(auto q:fvv)
	if(ans[q]==l)
	{
    	if(dp[q]>=0)ans[q]=mi,fvv1.emplace_back(q);
    	else fvv2.emplace_back(q);
	}
	// dbg(ans);
    if(round+1==lim)return;
    {
        for(auto q:fvv)
        key[q]=0,son[round+1][q].clear();
        vector<int>tmp=fvv1;
        for(int x=1;x<fvv1.size();x++)
        tmp.emplace_back(lca(fvv1[x-1],fvv1[x]));
        for(auto q:tmp)
        key[q]=1;
		fvv1.clear();
		for(auto q:fvv)
		if(key[q])fvv1.emplace_back(q);
        ::mi=mi,::l=l,::r=r;
        calcw2(round+1,fvv[0]);
        for(int x=1;x<fvv1.size();x++)
        {
            int l=lca(fvv1[x-1],fvv1[x]);
            son[round+1][l].emplace_back(fvv1[x]);
        }
        solve(mi,r,round+1,fvv1);
    }
    {
        for(auto q:fvv)
        key[q]=0,son[round+1][q].clear();
        vector<int>tmp=fvv2;
        for(int x=1;x<fvv2.size();x++)
        tmp.emplace_back(lca(fvv2[x-1],fvv2[x]));
        for(auto q:tmp)
        key[q]=1;
		fvv2.clear();
		for(auto q:fvv)
		if(key[q])fvv2.emplace_back(q);
        ::mi=mi,::l=l,::r=r;
        calcw1(round+1,fvv[0]);
        for(int x=1;x<fvv2.size();x++)
        {
            int l=lca(fvv2[x-1],fvv2[x]);
            son[round+1][l].emplace_back(fvv2[x]);
        }
        solve(l,mi,round+1,fvv2);
    }
}
int main()
{
    int n;
    cin>>n;
    for(int x=2;x<=n;x++)
    {
        cin>>fa[x];
        son[0][fa[x]].emplace_back(x);
    }
    dfs0(1,0);
    for(int x=1;1<<x<=n;x++)
    for(int y=1;y+(1<<x)-1<=n;y++)
    st[x][y]=tmin(st[x-1][y],st[x-1][y+(1<<x-1)]);
    vector<int>fvv;
    for(int x=1;x<=n;x++)
    cin>>w[0][x].first,w[0][x].second=1,fvv.emplace_back(x),ans[x]=1;
    sort(fvv.begin(),fvv.end(),[&](auto u,auto v){return dfn[u]<dfn[v];});
    solve(1,up,0,fvv);
    for(int x=1;x<=n;x++)
    cout<<ans[x]<<endl;
	cerr<<1.*clock()/CLOCKS_PER_SEC<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 15ms
memory: 92352kb

input:

2000
1 2 2 4 5 2 3 6 4 2 7 2 8 14 8 12 1 14 4 14 8 18 9 2 7 22 20 22 14 29 28 16 6 21 23 6 21 14 13 9 1 4 18 13 2 39 21 33 18 20 38 27 27 1 49 5 51 3 31 24 10 42 2 44 13 9 35 66 27 60 67 59 29 40 53 2 33 43 26 43 62 16 78 45 14 10 73 69 41 35 25 26 2 70 54 1 54 48 5 36 44 28 90 29 51 51 93 82 95 45 ...

output:

883838653.6806144714
887174606.4360675812
881024837.6128716469
912609577.2663455009
872318267.9499473572
831791401.0776324272
867874622.4770960808
892392158.6159086227
836427211.9250473976
869519710.6712517738
693335533.4487543106
925100803.4501433372
994728088.3841781616
950304508.2589240074
808672...

result:

ok 2000 numbers

Test #2:

score: 10
Accepted
time: 7ms
memory: 72056kb

input:

2000
1 1 1 1 1 6 6 6 8 1 7 6 9 4 11 10 17 1 9 20 4 2 7 22 13 21 5 26 19 20 9 8 24 22 32 24 24 8 30 7 22 22 7 14 4 18 30 38 9 45 21 38 53 16 39 6 44 12 10 34 14 17 54 14 65 55 17 21 40 9 27 65 54 53 61 30 3 52 57 49 31 34 16 32 11 85 81 43 36 43 3 45 42 93 83 37 86 77 2 23 41 77 19 18 51 91 68 22 85 ...

output:

794920921.5307626724
713824749.2790951729
734115600.8518218994
800547123.1547751427
734508037.8326306343
760946274.0427646637
750093460.3329143524
735976696.2784276009
765501022.5733661652
747665882.3629298210
816306114.3804712296
741937637.5871639252
790935993.4036440849
784790992.9520254135
686615...

result:

ok 2000 numbers

Test #3:

score: 10
Accepted
time: 19ms
memory: 77912kb

input:

2000
1 1 2 3 3 3 3 4 2 8 4 6 2 10 1 8 8 13 1 19 15 18 8 17 20 16 16 21 11 28 14 18 31 4 30 24 17 10 22 26 2 34 14 13 13 37 43 3 3 38 9 4 29 43 29 46 7 55 9 23 23 49 29 12 45 25 67 59 45 24 5 55 52 73 51 28 25 26 49 78 62 10 18 1 35 73 35 16 52 62 5 89 4 49 12 46 55 14 18 68 64 25 21 88 25 19 82 46 4...

output:

755177498.1085920334
762060165.6432132721
754126549.0129632950
777332782.9680285454
758702755.2156624794
756576061.4922032356
764145851.3711080551
750062465.9176621437
710728645.6139783859
770350933.3046002388
769495010.6064815521
776873111.9479804039
763361454.2466483116
718961239.1421227455
691159...

result:

ok 2000 numbers

Test #4:

score: 10
Accepted
time: 18ms
memory: 88232kb

input:

2000
1 1 3 4 1 1 4 3 3 2 1 3 11 3 1 7 17 9 7 18 4 5 16 10 16 14 12 6 16 22 28 32 27 4 4 19 36 38 12 31 28 18 30 44 35 43 44 29 10 29 7 18 18 35 23 42 12 24 23 2 42 59 8 24 14 49 16 62 38 46 7 34 41 41 10 20 53 71 18 38 63 54 26 76 39 84 28 36 9 53 26 19 39 34 26 49 86 10 64 34 74 43 19 70 97 35 92 4...

output:

914893627.2518544197
918140888.2959704399
911927223.2936391830
870659351.4782176018
777969360.5735931396
778920650.7032570839
876560688.1422381401
974454879.7862873077
858643055.1035151482
835985660.7169928551
963418960.6078701019
868819713.7237095833
813377857.3948740959
984874725.3569221497
762109...

result:

ok 2000 numbers

Test #5:

score: 10
Accepted
time: 15ms
memory: 88208kb

input:

2000
1 2 2 3 2 1 7 8 8 6 9 12 12 3 8 3 9 15 3 19 8 7 4 19 18 23 10 21 10 15 10 22 1 21 19 26 1 38 38 1 18 37 14 27 37 43 30 4 2 2 13 42 13 9 13 38 21 23 58 32 13 62 18 62 15 49 5 61 1 45 29 48 38 34 31 43 45 38 52 54 13 21 78 36 21 45 57 14 25 18 29 45 2 43 8 51 75 79 95 55 29 98 55 93 33 5 93 14 77...

output:

865975380.0778722763
864960193.7690730095
853815078.8815364838
725289345.0623083115
835913658.3061761856
751151085.1487512589
880779266.4766426086
883843422.0521917343
866946220.5310029984
875695228.7009649277
798984050.9517483711
869102478.1582412720
879836559.4158177376
911091804.5933027267
850227...

result:

ok 2000 numbers

Test #6:

score: 10
Accepted
time: 15ms
memory: 82396kb

input:

2000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...

output:

780031204.4436016083
709196090.9890460968
852015972.2854351997
710198402.6945867538
942523002.6819887161
795582294.6685290337
817131519.5004954338
723247528.3529243469
711787224.1041307449
702697754.2035522461
778947830.4212474823
825829506.0945806503
731540203.3629422188
717837810.7985196114
755917...

result:

ok 2000 numbers

Test #7:

score: 10
Accepted
time: 11ms
memory: 64300kb

input:

2000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...

output:

621160984.4181456566
460347414.5563762188
624969959.6340632439
386751413.9585855007
463912964.4032745361
565083980.9952187538
628866196.0498447418
344826222.1212382317
389755726.4708399773
428515911.6737790108
467519999.0828950405
517598152.6430463791
569478035.4036664963
614133358.3875756264
633756...

result:

ok 2000 numbers

Test #8:

score: 10
Accepted
time: 12ms
memory: 80664kb

input:

2000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...

output:

621373653.7904915810
487030029.8098449707
624597072.9767212868
939363956.5120520592
480110168.9769210815
578609943.8112826347
628514290.2274427414
497600079.0851635933
398302078.8487682343
430778027.1500325203
483843803.9219179153
534426689.6135225296
585697651.3237261772
623651504.8929500580
634658...

result:

ok 2000 numbers

Test #9:

score: 10
Accepted
time: 18ms
memory: 78492kb

input:

2000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...

output:

762088775.8726768494
781352997.0448188782
714336395.5493354797
723995685.8533968925
787378788.2070059776
708370685.8690218925
735529899.8616380692
725933552.0623965263
721087932.8655819893
810402393.5306620598
798069954.1203870773
761321544.8858952522
708378792.1007032394
806706905.5582833290
682416...

result:

ok 2000 numbers

Test #10:

score: 10
Accepted
time: 15ms
memory: 82500kb

input:

2000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...

output:

796409130.3000264168
777105331.6437931061
719995022.1000733376
755696296.9361982346
972657203.7016592026
705728054.3409028053
822339058.1000242233
756513595.8245410919
858700275.5624423027
980361938.4962005615
924539089.2783417702
708454132.3716239929
722157955.4475197792
856914520.4067573547
691671...

result:

ok 2000 numbers

Test #11:

score: 10
Accepted
time: 12ms
memory: 84136kb

input:

2000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

984618186.9660654068
902276992.8955745697
383235455.1760907173
742640495.5576524734
613666534.8101615906
291453123.8011982441
625936985.3899321556
958738327.0676288605
34831703.6743662953
240996838.3749699593
334863663.3848628998
223278761.6867554188
111864210.0632456541
669194698.6645455360
1725111...

result:

ok 2000 numbers

Test #12:

score: 10
Accepted
time: 14ms
memory: 63468kb

input:

2000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

506787300.6030759811
507472992.4358863831
508859158.0533967018
556160450.4255290031
620472431.5623888969
867793083.3231248856
786221981.2623620033
511025429.2609472275
532980919.3512964249
612986088.1860861778
767631530.9940872192
992646217.3535451889
966889381.4418020248
550282478.7822370529
558374...

result:

ok 2000 numbers

Test #13:

score: 10
Accepted
time: 8ms
memory: 64936kb

input:

2000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

470231533.5803055763
470466375.8804857731
470701218.1806659698
470936537.3180038929
471171618.0367629528
471407175.5926797390
471642733.1485965252
471878290.7045133114
472114086.6790089607
472349644.2349257469
472585201.7908425331
472820282.5096015930
473055363.2283606529
473290205.5285408497
473524...

result:

ok 2000 numbers

Test #14:

score: 10
Accepted
time: 16ms
memory: 65280kb

input:

2000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

483978748.8375544548
484220505.2765216827
484462738.5526466370
484704018.1544561386
484945297.7562656403
485187054.1952328682
485427856.9598846436
759340286.4955425262
485532284.2974267006
485773563.8992362022
485873222.8652009964
486114979.3041682243
486356258.9059777260
486598015.3449449539
486839...

result:

ok 2000 numbers

Test #15:

score: 10
Accepted
time: 15ms
memory: 67496kb

input:

2000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

685495376.9014186859
869311809.6704831123
517162800.3180422783
526888847.8241853714
654153347.3612275124
547770023.7981772423
569561958.7434263229
819660186.9479179382
847532749.3284926414
564797878.7005829811
855185508.8728418350
585505009.1120047569
854052543.7860841751
868020057.8102025986
543898...

result:

ok 2000 numbers

Test #16:

score: 10
Accepted
time: 18ms
memory: 65428kb

input:

2000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

491106510.6712470055
494822502.6414079666
501410484.8125543594
504759312.1712660789
512058735.3817400932
513949394.7121248245
522550106.5260338783
915653705.6812701225
537904739.8419780731
581374645.6517796516
920748710.7115755081
597709179.3268513680
913259506.3123264313
611387253.1962299347
733489...

result:

ok 2000 numbers

Test #17:

score: 10
Accepted
time: 19ms
memory: 89156kb

input:

2000
1 1 3 3 2 5 4 2 1 5 7 1 7 5 11 7 13 15 15 18 12 17 13 19 15 12 25 18 24 30 30 23 19 20 32 36 25 27 30 37 28 33 34 35 31 38 35 45 48 50 48 50 40 45 43 49 53 53 52 54 61 56 53 63 60 58 54 58 68 68 69 68 70 73 62 71 71 77 69 69 71 74 72 76 79 80 81 83 75 86 90 86 91 91 91 85 90 88 99 90 94 91 102 ...

output:

734060764.5786833763
907169818.9710040092
884436607.4764032364
248349190.5099515915
731751442.2238149643
122787834.0910183191
631204128.6341767311
3817026.5682445131
52135170.4539378285
803279876.9057044983
259513617.3023760319
590964794.5679707527
628669262.3037037849
438379049.8627684116
824486732...

result:

ok 2000 numbers

Test #18:

score: 10
Accepted
time: 12ms
memory: 81232kb

input:

2000
1 1 1 3 1 5 1 7 6 6 8 3 9 7 14 2 7 7 11 7 13 19 19 12 16 13 18 16 19 23 18 32 24 34 32 31 28 34 26 31 41 28 42 30 33 43 47 38 49 38 49 40 41 49 44 45 54 52 51 53 55 59 52 61 52 61 65 65 60 58 62 68 73 65 71 76 64 71 68 73 67 75 73 75 75 80 81 76 76 87 77 85 93 82 93 84 89 97 88 89 96 102 92 100...

output:

712000847.1507921219
4201357.3173719011
713061809.8267331123
2244052.5436143316
714122772.5026741028
5225145.3214617148
715187073.0387191772
5869203.3099381402
716256141.9463415146
3957451.3859046102
6429323.0574935600
7157174.0005694963
8323916.2944295332
717329502.3883833885
7273391.8818943948
718...

result:

ok 2000 numbers

Test #19:

score: 10
Accepted
time: 26ms
memory: 83280kb

input:

2000
1 1 1 2 1 6 2 5 1 2 9 11 1 13 10 12 5 5 13 13 14 17 14 22 13 15 16 16 28 21 31 18 26 21 21 26 34 28 39 31 36 32 34 40 34 40 44 46 46 46 50 47 45 53 42 42 46 46 49 47 60 62 59 61 59 59 66 63 67 60 62 70 68 64 62 70 68 70 79 76 81 75 80 70 80 85 85 85 85 83 80 88 89 92 83 90 93 95 99 93 100 88 89...

output:

697495937.6499161720
698611259.7618379593
143289805.3153283596
1583425.3952294914
9656027.9497632235
2424101.4114943948
2532740.1897146516
3850669.6648962796
7472195.7237633094
518529892.4492435455
699729442.8967061043
8643687.7627491355
700410366.3579392433
550988674.6128296852
10028393.0664639175
...

result:

ok 2000 numbers

Test #20:

score: 10
Accepted
time: 11ms
memory: 83168kb

input:

2000
1 1 1 3 1 4 3 7 5 6 7 3 7 8 10 6 13 4 12 18 16 16 10 15 20 18 15 24 15 19 24 21 32 22 25 25 33 30 37 37 40 29 31 32 40 39 44 38 39 45 50 52 46 45 48 45 46 47 56 48 51 49 63 51 57 63 61 57 58 58 64 61 63 60 61 63 71 77 66 78 77 70 81 70 85 80 83 84 84 77 78 86 84 85 91 82 83 85 92 92 88 92 101 1...

output:

788364410.6120262146
291116715.1864223480
705269336.9951701164
968496322.6633396149
479210854.0974493027
984278678.9097642899
749238491.3091111183
650055885.6648855209
330485106.1840412617
502037048.8378067017
306298018.1955330372
306940317.8469903469
516159534.9381861687
428612948.0353763103
666892...

result:

ok 2000 numbers

Test #21:

score: 10
Accepted
time: 11ms
memory: 80956kb

input:

2000
1 1 3 4 1 4 7 3 9 5 1 6 8 5 12 16 6 12 13 15 11 15 13 17 20 21 14 14 21 19 22 18 30 25 28 36 26 24 37 34 40 39 43 44 37 44 44 36 49 38 40 51 48 42 49 47 53 48 51 58 48 62 57 59 65 59 65 59 57 69 63 62 64 70 72 75 64 77 70 68 71 80 78 77 79 78 87 86 86 84 84 89 84 84 88 92 91 85 98 99 101 90 96 ...

output:

652426243.1759428978
506709099.3092088699
626941204.4441037178
640221596.1239385605
530323029.0341300964
829463958.9107704163
531001091.4724168777
577506065.7911462784
991901397.7131767273
1000661.4706175150
123643279.9519792795
660009861.3324217796
658531666.1434702873
806631565.2873625755
55044651...

result:

ok 2000 numbers

Test #22:

score: 10
Accepted
time: 15ms
memory: 81000kb

input:

2000
1 2 3 4 4 3 7 3 9 7 7 9 12 14 4 7 1 18 7 6 19 11 21 24 23 15 22 3 1 14 9 24 26 14 9 8 1 32 21 13 11 4 3 4 25 24 18 10 9 36 10 18 53 25 6 26 19 26 44 29 34 56 40 63 60 43 50 63 52 64 59 56 62 52 50 72 47 55 67 48 55 54 53 44 57 81 44 64 49 61 44 43 52 78 91 60 48 71 74 78 83 63 72 64 96 59 75 77...

output:

661041260.1045837402
709911823.5627932549
738067150.3778996468
723578930.1775441170
671235084.8624563217
661735535.0062332153
661571979.8611330986
592983246.2566261292
616968155.2902584076
649054050.7965025902
777022361.9783487320
455883026.6671638489
297814369.9038457870
627502441.7787475586
547794...

result:

ok 2000 numbers

Test #23:

score: 10
Accepted
time: 22ms
memory: 79152kb

input:

2000
1 2 1 1 3 3 5 3 1 8 3 7 12 2 6 13 6 18 1 4 17 12 5 4 4 8 9 21 24 17 13 26 3 9 23 28 9 38 18 1 29 35 14 43 40 23 46 25 13 30 40 23 7 45 39 39 28 58 24 32 31 56 39 35 21 26 27 48 39 65 52 24 45 39 52 62 66 30 64 45 60 56 67 57 47 56 47 49 70 51 67 47 51 64 66 79 70 80 92 64 73 68 63 61 64 79 107 ...

output:

784494400.2399196625
728336334.5001792908
730864048.2732863426
787670135.7103767395
53300173.0372302234
24228424.8096186221
97778917.2611688375
37729174.8609677255
733404159.8124942780
6499712.4176126085
6922126.8094230890
25869385.3821277469
102971733.5134528279
13920337.9478258789
7950023.80870799...

result:

ok 2000 numbers

Test #24:

score: 10
Accepted
time: 15ms
memory: 83056kb

input:

2000
1 2 1 4 4 3 3 4 6 2 5 10 11 9 11 16 13 12 6 12 19 12 14 9 23 8 8 28 5 14 21 20 8 5 5 16 9 33 39 24 25 3 19 29 15 7 46 39 32 42 45 13 34 40 21 29 29 39 18 59 59 18 43 37 29 43 31 22 66 40 47 47 56 25 58 60 62 68 51 41 51 42 64 46 54 84 85 52 74 70 67 48 76 49 89 82 69 49 77 58 62 75 99 100 102 7...

output:

783352852.0843229294
204903126.5580363274
229172707.3748311996
785254001.8321776390
16952634.8407744169
329675436.6902220249
199435354.0796784163
182894349.9153112173
787160396.7887673378
484557152.3098764420
15562267.0958116353
18638358.5014650971
965692520.1759090424
17293126.3737133443
789093494....

result:

ok 2000 numbers

Test #25:

score: 10
Accepted
time: 15ms
memory: 83024kb

input:

2000
1 1 2 1 2 3 5 8 9 4 9 1 1 9 8 6 8 1 8 9 14 16 7 4 10 13 19 24 21 23 6 3 28 21 8 33 21 17 26 20 25 27 11 28 21 42 32 27 16 30 28 29 31 25 8 51 31 54 12 38 15 23 21 28 42 33 30 54 38 33 53 71 71 33 38 74 45 57 77 69 76 80 81 64 51 66 83 52 75 49 47 86 74 52 81 53 66 65 72 86 57 73 69 100 96 96 70...

output:

712379455.8540267944
730937481.1955761909
594520569.2531356812
783451557.3759722710
750107765.4476461411
327405691.8194448948
533642769.3262205124
760578155.7569999695
716674328.1336674690
530704021.9231534004
873840332.1574096680
558880329.5731997490
700766086.8776030540
681959629.3768782616
625729...

result:

ok 2000 numbers

Test #26:

score: 10
Accepted
time: 15ms
memory: 80924kb

input:

2000
1 2 2 3 3 3 7 2 6 2 8 4 13 14 1 8 13 17 13 15 13 10 11 22 24 12 22 16 6 6 10 14 13 30 10 25 27 20 37 5 13 27 14 19 21 1 24 42 21 36 36 4 46 30 41 41 51 22 10 15 22 19 27 28 20 42 42 47 22 58 68 37 56 63 51 40 36 45 40 59 62 56 73 58 62 45 75 87 78 63 67 66 48 49 51 68 85 68 55 64 64 88 98 80 99...

output:

862102985.5199770927
646331310.6258854866
647879600.8770227432
937930584.0159268379
846045494.2335443497
653605461.4670000076
647401333.2078232765
763227463.0053272247
356420994.4485106468
664412498.8097085953
583588600.5751028061
678335190.1410007477
656738758.4304194450
502026081.5831789970
594368...

result:

ok 2000 numbers

Test #27:

score: 10
Accepted
time: 16ms
memory: 92848kb

input:

2000
1 2 1 1 5 3 2 3 2 2 5 12 7 12 14 5 8 7 15 11 2 2 1 17 21 13 6 19 16 17 7 24 29 23 7 9 4 17 18 22 16 30 4 44 18 4 44 33 41 30 2 1 50 39 8 52 54 25 18 25 57 8 39 14 10 19 49 50 28 28 29 60 15 28 65 3 43 70 16 52 65 47 30 34 37 51 54 55 86 39 70 87 86 80 27 54 6 93 75 93 98 18 68 85 60 98 45 18 78...

output:

822926044.6411852837
836531639.2625894547
864103317.3966388702
725944996.1541819572
779930114.9661636353
789866447.6588640213
724644661.2250623703
905205249.8811717033
849643707.4257469177
801687240.7988986969
801268577.7744150162
734014988.2115416527
639833450.6775493622
726742744.7190580368
952865...

result:

ok 2000 numbers

Test #28:

score: 10
Accepted
time: 7ms
memory: 72460kb

input:

2000
1 1 1 4 5 1 3 5 3 5 6 2 4 1 9 13 11 11 7 6 16 9 4 16 14 12 4 2 24 16 5 22 17 22 13 24 25 38 1 7 6 18 2 42 19 43 19 23 3 47 14 45 30 37 25 9 44 44 11 55 51 7 8 21 33 66 49 63 9 53 21 13 58 21 37 63 4 31 60 65 52 7 10 18 68 20 43 53 45 62 85 64 40 41 35 7 72 50 89 85 57 49 90 93 60 63 44 37 8 85 ...

output:

618462086.1054148674
567825794.6521449089
567302227.4529614449
619847298.0486097336
628078937.9024386406
587316036.6370491982
576029777.9508256912
592046738.0788516998
572319984.8637151718
534341812.5994472504
562681675.3945937157
572745800.4455647469
580113411.3695936203
559118271.3149051666
538947...

result:

ok 2000 numbers

Test #29:

score: 10
Accepted
time: 12ms
memory: 76548kb

input:

2000
1 2 1 3 3 5 1 8 2 2 7 10 9 5 7 16 5 2 10 18 18 14 16 24 7 14 24 2 10 11 19 29 2 16 12 18 19 5 16 10 35 12 37 14 28 20 10 8 38 8 22 9 33 16 3 14 22 47 18 32 56 58 6 22 22 39 36 33 17 40 10 46 29 17 17 11 11 21 62 20 51 7 47 52 83 81 7 60 61 83 42 69 82 77 48 77 44 58 23 23 29 33 63 63 102 49 36 ...

output:

640682220.8183021545
654793739.6640539169
623723984.1409244537
563367844.0645618439
629995823.2764983177
578004837.4581279755
644883633.0150284767
609658241.6623144150
627572060.0037755966
666070461.6071228981
552742481.6789469719
596053600.7152256966
709927559.1889982224
627611160.6507091522
589146...

result:

ok 2000 numbers

Test #30:

score: 10
Accepted
time: 22ms
memory: 82684kb

input:

2000
1 2 1 4 5 2 5 8 5 3 4 11 3 4 9 1 4 11 14 18 19 11 21 13 22 9 15 13 14 24 9 22 31 33 23 16 33 19 34 21 10 40 40 28 30 24 9 45 28 28 20 2 12 15 22 55 54 10 18 25 56 24 42 28 36 13 63 48 49 34 16 56 1 14 27 1 1 31 43 50 71 20 61 72 50 57 53 11 15 65 2 1 24 87 33 77 33 54 26 91 43 12 53 44 6 101 95...

output:

875749588.1369457245
980774879.4747915268
792393684.5948133469
877334594.8492279053
892872333.6337389946
692916870.4242706299
844673156.8936080933
968336105.3783435822
809406757.5453295708
841448307.1959052086
802109241.6834864616
822804451.1659650803
689116478.2771921158
820686817.3485026360
800229...

result:

ok 2000 numbers

Test #31:

score: 10
Accepted
time: 12ms
memory: 80492kb

input:

2000
1 2 3 2 1 5 2 7 1 10 6 2 11 4 3 16 10 3 14 12 3 22 9 15 11 11 17 6 16 15 14 14 1 15 32 14 16 29 25 31 3 24 26 37 3 24 38 24 46 5 13 7 31 3 3 32 42 18 16 5 46 60 57 33 34 55 42 23 63 26 57 62 32 40 57 75 47 73 37 28 57 70 78 6 82 86 61 53 17 60 3 7 19 10 36 72 55 95 45 5 15 22 34 57 105 58 18 69...

output:

947322368.6745038033
829209327.8685445786
924969673.2317686081
856705188.8945155144
797400474.7509393692
800729751.7861843109
740208626.0532484055
711780071.5467648506
712300300.8858442307
992630958.5644979477
993761062.6283092499
770162105.7901406288
636860370.9991259575
797242641.6517319679
782755...

result:

ok 2000 numbers

Subtask #2:

score: 0
Time Limit Exceeded

Test #32:

score: 0
Time Limit Exceeded

input:

200000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

output:

792545318.8109703064
794937133.9941253662
794842720.2368955612
804131031.2322459221
805846214.4885873795
806375980.5708212852
778037071.4499902725
815562248.4144182205
776087761.1492052078
809328556.2514624596
767722606.8912129402
771619320.1441521645
800107479.2953515053
879639625.6696767807
775670...

result:


Subtask #3:

score: 40
Accepted

Dependency #1:

100%
Accepted

Test #37:

score: 40
Accepted
time: 167ms
memory: 129128kb

input:

50000
1 2 2 1 3 5 3 8 6 9 10 4 3 8 9 11 14 9 9 13 8 3 14 10 1 21 12 18 27 13 24 11 33 19 34 26 33 21 19 19 40 22 12 32 29 33 12 11 42 48 51 16 51 17 7 5 49 21 50 58 16 37 15 30 6 43 22 63 22 33 56 52 14 45 75 12 66 1 70 78 46 7 8 10 21 68 9 85 40 51 73 17 48 74 57 62 14 51 21 79 74 58 66 13 94 46 3 ...

output:

971673011.8081121445
975121498.1327886581
969074249.2985038757
975663185.1439657211
960156440.7747068405
968562126.1911058426
960213661.2336339951
971200943.0219631195
967905998.2620744705
967353820.8334274292
970195770.2934761047
966188430.8199443817
959924697.9160518646
973710060.1459188461
952172...

result:

ok 50000 numbers

Test #38:

score: 40
Accepted
time: 136ms
memory: 104536kb

input:

50000
1 1 3 1 5 5 6 7 9 6 7 8 7 14 10 13 14 14 2 16 17 5 7 18 10 9 21 11 8 14 25 18 9 13 32 14 17 36 1 33 27 8 25 34 12 14 31 15 9 21 31 33 48 34 47 24 43 25 57 56 1 8 20 6 25 4 36 8 23 64 35 53 10 57 49 48 57 29 70 20 19 7 34 81 47 80 30 15 47 16 42 85 69 83 83 92 86 63 66 50 38 53 10 44 69 8 1 2 8...

output:

942224502.6212520599
938591957.1536931992
937275886.5983686447
939689636.2907791138
942753791.8663282394
942778110.5613722801
943084716.8537902832
939757824.0043339729
943330764.8271770477
947373867.0875382423
940465450.3463997841
928695201.9450840950
940003871.9777207375
942767620.1439023018
944213...

result:

ok 50000 numbers

Test #39:

score: 40
Accepted
time: 136ms
memory: 110620kb

input:

50000
1 1 1 1 2 1 1 7 6 8 4 12 3 4 11 14 6 15 11 15 20 4 9 9 25 21 9 11 4 30 19 28 28 6 16 7 32 16 33 4 4 41 18 31 14 26 43 38 9 26 33 22 42 17 25 4 56 55 39 30 50 61 35 46 21 56 41 14 46 18 20 22 6 48 16 67 17 14 1 2 43 37 23 48 70 57 20 47 43 8 66 22 24 18 54 49 33 38 19 79 82 35 39 3 87 53 11 30 ...

output:

944712162.0731101036
941099643.7661757469
943431854.3046150208
949572086.3846564293
928087234.5689830780
938832759.9183449745
944590091.7607321739
941495418.6070885658
938971042.6940855980
936957836.2141652107
942148208.6760158539
943199634.6088023186
939936637.9384813309
941081047.1170244217
947563...

result:

ok 50000 numbers

Test #40:

score: 40
Accepted
time: 143ms
memory: 120852kb

input:

50000
1 2 1 4 2 5 4 4 5 1 3 5 2 7 2 10 16 10 4 6 17 8 11 22 17 19 24 13 18 6 17 4 20 14 16 14 13 8 37 3 26 12 2 11 3 32 26 45 2 32 47 12 1 16 54 38 4 38 46 38 5 58 62 62 48 31 54 7 15 29 59 28 1 15 41 70 54 3 74 33 29 79 80 65 47 84 83 72 52 69 38 68 87 77 6 67 22 9 49 65 54 16 65 88 15 50 86 36 85 ...

output:

953956604.0499496460
955753326.4602622986
961680412.3308000565
948605537.4659452438
948678970.3882350922
943894863.1847672462
944979190.8814368248
955746650.7400541306
943244934.1387863159
952594280.2903256416
951420307.2080035210
967090606.7223625183
946559906.0592994690
937133312.2882084846
939003...

result:

ok 50000 numbers

Test #41:

score: 40
Accepted
time: 159ms
memory: 124968kb

input:

50000
1 2 1 2 1 5 2 1 7 2 10 7 6 13 15 13 16 9 3 3 3 9 7 5 4 5 9 12 17 7 18 15 8 16 8 25 18 13 25 38 37 40 31 33 37 5 45 44 17 38 13 33 27 7 6 36 1 43 20 51 10 37 29 55 51 22 45 43 62 68 16 72 14 37 63 71 3 44 26 43 79 11 29 63 64 23 65 37 46 40 78 14 18 33 37 8 72 31 42 4 97 100 1 54 92 95 39 52 4 ...

output:

964561462.4377822876
964711189.3053083420
962409973.1821212769
974364280.7263193130
965759277.3779907227
954598426.8642492294
967457771.3338117599
954314231.9182443619
958655357.4021844864
981997489.9472017288
962842941.3213367462
953611373.9477558136
971175193.8154459000
955700874.3729124069
962610...

result:

ok 50000 numbers

Test #42:

score: 40
Accepted
time: 217ms
memory: 134056kb

input:

50000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...

output:

773863315.8084120750
775841713.1758184433
830246925.5237569809
842347622.0753769875
791235447.1386961937
909352779.4790749550
757149219.7557902336
735430240.8956732750
772128105.3914461136
932157039.7101769447
779289722.6633372307
817519664.9468846321
776673794.0160508156
824708938.7739238739
746307...

result:

ok 50000 numbers

Test #43:

score: 40
Accepted
time: 168ms
memory: 112128kb

input:

50000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...

output:

643577099.2028584480
633928299.3162670135
644133091.3287672997
519853115.5619339943
634545803.4355225563
644689560.2918338776
404473543.7626407146
461771727.1465046406
520359516.6234393120
577875614.5883841515
635164261.2290935516
645326614.7345561981
349798918.4205868244
377487183.2397003174
405260...

result:

ok 50000 numbers

Test #44:

score: 40
Accepted
time: 163ms
memory: 126664kb

input:

50000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...

output:

642875194.9066853523
632905483.6129441261
643430710.1954364777
520071030.1430149078
633522034.0578842163
643986702.3213453293
405725479.7202510834
464198113.0235948563
521080971.2430791855
578111648.9814586639
634139061.3399820328
644645691.2733230591
349462271.3872320652
378264189.3882153034
406252...

result:

ok 50000 numbers

Test #45:

score: 40
Accepted
time: 226ms
memory: 143664kb

input:

50000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...

output:

873087406.2853598595
647700310.1057176590
658685684.5454158783
891513824.5713768005
649538040.5115947723
658779621.4654879570
539422512.5150208473
554330349.4141755104
578772545.2820672989
609730720.9102888107
654111862.5285053253
661957264.2845759392
496887684.3715205193
525737762.9254341125
541354...

result:

ok 50000 numbers

Test #46:

score: 40
Accepted
time: 236ms
memory: 134120kb

input:

50000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...

output:

767297268.1465210915
767742157.2146797180
741038799.5448498726
761869430.7801227570
768896103.1363773346
974861145.0446701050
747382641.0912404060
764374256.3696589470
770469188.9197163582
756494045.5010743141
775626182.7805261612
743592262.5244741440
738873482.0116147995
724634647.6447501183
774840...

result:

ok 50000 numbers

Test #47:

score: 40
Accepted
time: 134ms
memory: 126912kb

input:

50000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

994962692.2657794952
283414126.1590907574
428236246.6807725430
216320157.8347662687
799276352.1294345856
187955141.8795497417
516402721.8886265755
561769485.9118633270
351055145.9126167297
587866306.7170653343
876382827.8824062347
487670898.9498291016
905102253.0551028252
690357208.5615959167
508059...

result:

ok 50000 numbers

Test #48:

score: 40
Accepted
time: 222ms
memory: 146076kb

input:

50000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

output:

743118286.3896942139
797411442.0055670738
882130622.9816389084
551625252.2183942795
617260456.4679446220
978413581.8697309494
670400619.8364353180
889144420.7346348763
620523453.1382656097
745552540.0798869133
758151531.4613308907
767371177.9059686661
480448723.3589067459
499843597.9122657776
690136...

result:

ok 50000 numbers

Test #49:

score: 40
Accepted
time: 121ms
memory: 133136kb

input:

50000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

output:

477091312.9313559532
477100849.6745104790
477110386.4176650047
477119923.1608195305
477129459.9039740562
477138996.6471285820
477148533.3902831078
477158546.9705953598
477168083.7137498856
477177620.4569044113
477187157.2000589371
477196693.9432134628
477206230.6863679886
477215767.4295225143
477225...

result:

ok 50000 numbers

Test #50:

score: 40
Accepted
time: 119ms
memory: 137372kb

input:

50000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

output:

475254059.3626365662
475263357.6872122288
475272894.4303667545
475282431.1735212803
475291967.9166758060
475301504.6598303318
475311041.4029848576
475320578.1461393833
475329876.4707150459
475339413.2138695717
475348949.9570240974
475358486.7001786232
475368023.4433331490
475377560.1864876747
475387...

result:

ok 50000 numbers

Test #51:

score: 40
Accepted
time: 157ms
memory: 147416kb

input:

50000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

output:

475549459.9818480015
475558996.7250025272
475568533.4681570530
475577831.7927327156
475587368.5358872414
475596905.2790417671
475606442.0221962929
475615978.7653508186
475623369.7412955761
475632906.4844501019
475635767.5073964596
827691555.1955018044
475638390.1117639542
531899929.5147309303
839020...

result:

ok 50000 numbers

Test #52:

score: 40
Accepted
time: 223ms
memory: 147936kb

input:

50000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

output:

692670345.6137261391
919601440.5100860596
928187847.2092633247
937096595.8270635605
676499367.0837545395
739252090.7148494720
820447445.0953240395
981753349.3224458694
794630050.8645496368
684742451.0293688774
765115261.3127655983
786193847.8700561523
801795959.6708602905
823895931.4200005531
995811...

result:

ok 50000 numbers

Test #53:

score: 40
Accepted
time: 294ms
memory: 151316kb

input:

50000
1 1 1 1 5 3 1 3 8 9 7 2 13 12 3 12 12 14 19 17 14 14 22 20 14 18 21 22 26 17 31 23 27 23 22 35 37 26 32 40 38 29 40 32 41 33 43 38 43 43 41 50 51 45 48 50 51 58 49 50 58 52 59 55 59 56 63 68 58 69 71 70 61 68 65 76 77 65 69 74 73 69 72 74 78 79 79 85 80 86 81 80 93 90 86 95 96 94 87 97 93 99 9...

output:

869081497.3233013153
873980045.4446234703
686873913.1244053841
717233658.1196804047
962868690.5278539658
533957005.0131621361
774012089.0016226768
763400554.8935818672
555181026.9035592079
135641337.3053987026
761689663.1716599464
927614212.1085186005
982061386.1263370514
998383522.0353078842
755995...

result:

ok 50000 numbers

Test #54:

score: 40
Accepted
time: 170ms
memory: 161932kb

input:

50000
1 1 1 3 1 6 7 1 9 6 3 8 13 13 10 14 3 9 11 17 7 10 18 13 18 21 24 21 15 19 27 22 33 25 25 22 30 28 26 32 28 40 41 34 45 37 38 35 46 43 51 40 50 46 45 47 53 46 56 47 56 55 51 61 61 62 54 56 57 64 58 58 69 70 69 73 67 74 66 68 70 79 77 76 83 72 78 87 76 79 91 83 93 88 88 85 96 89 92 87 94 91 101...

output:

721592903.4156141281
38323.9925845293
2980287.2524985727
68271.9505098822
71660.9751478580
721633911.4111785889
721674919.4067430496
446224.8862373594
306579.8184020794
287033.2202255963
260023.4686048953
220045.9814682161
482979.7644384480
433109.3032628088
493669.4849391948
327620.9564786821
46372...

result:

ok 50000 numbers

Test #55:

score: 40
Accepted
time: 171ms
memory: 166092kb

input:

50000
1 1 1 3 4 3 7 8 6 7 8 11 8 1 9 5 15 14 9 20 12 17 21 12 17 15 17 20 16 19 31 21 22 29 24 25 27 36 32 29 33 29 37 43 43 43 42 46 42 43 46 49 50 51 42 47 55 53 47 52 49 51 55 57 54 57 66 57 60 60 65 72 59 72 63 74 63 68 75 79 67 71 79 77 72 80 83 86 84 77 77 80 86 81 90 89 88 91 93 86 93 102 98 ...

output:

724780559.8150143623
10181.9928208294
724822044.6477365494
67517.6374328589
172802.5484422965
83802.4529179957
724864006.3176164627
724905967.9874963760
724947929.6573762894
99577.9513706491
110474.4836904146
342190.1011601102
112339.9810131648
297874.9791364970
275288.3112488654
202897.8881649348
2...

result:

ok 50000 numbers

Test #56:

score: 40
Accepted
time: 247ms
memory: 155064kb

input:

50000
1 2 2 2 5 1 5 6 9 8 3 12 2 2 12 2 8 9 9 16 14 19 22 17 24 25 19 19 25 16 29 22 20 22 34 22 23 36 39 33 31 34 38 32 31 40 38 37 40 50 41 46 51 49 47 46 52 55 47 60 54 51 61 56 59 61 67 56 61 61 61 68 65 61 69 64 66 78 77 68 71 80 76 70 73 85 77 83 89 76 85 82 92 81 83 84 95 87 98 98 99 91 90 90...

output:

681227207.5026106834
681269169.1724905968
207865000.5632531643
59868.9761734952
681286812.1473264694
681328773.8172063828
89980.9632871381
461930752.3386063576
681370258.6499285698
100048.9677622899
110652.9483785968
242500544.3518598080
152967.9387599016
936716556.6123557091
816177368.3478851318
29...

result:

ok 50000 numbers

Test #57:

score: 40
Accepted
time: 286ms
memory: 157388kb

input:

50000
1 1 3 3 3 6 3 5 5 7 2 10 9 14 10 3 17 7 6 20 16 15 13 11 14 15 16 26 21 24 27 23 20 24 24 29 32 34 25 28 36 41 42 41 32 46 35 37 35 39 48 49 48 53 47 46 57 51 53 55 50 55 53 63 59 64 65 56 57 59 69 63 66 74 65 63 68 73 75 74 73 80 82 77 82 83 73 85 81 77 88 87 92 84 85 88 92 97 97 95 92 89 101...

output:

725863457.0002107620
253390551.3600127697
732100963.8604283333
56033105.6020937264
735122680.9289398193
729795933.0399794579
558773518.0498690605
452733278.8218028545
712061882.3069810867
753952026.6132354736
900828361.6104021072
369618178.0443222523
809489727.2107739449
995294570.9275569916
9395990...

result:

ok 50000 numbers

Test #58:

score: 40
Accepted
time: 287ms
memory: 159500kb

input:

50000
1 2 2 2 4 6 1 5 3 1 6 12 12 2 2 4 12 17 19 2 19 20 2 18 11 19 20 19 19 18 9 15 1 26 5 13 18 33 15 6 35 33 19 36 3 46 24 15 44 34 18 17 31 35 17 23 41 55 18 59 20 39 38 45 54 56 38 21 29 37 71 42 38 64 72 46 40 51 71 68 55 62 58 73 64 78 75 87 73 72 90 58 92 57 61 52 52 64 82 84 72 71 89 59 67 ...

output:

701457023.9191484451
740293503.0673236847
491323471.5780124664
694287777.2527337074
448059321.0017697811
726085186.2785534859
905995845.8886818886
801579952.4384102821
892797470.1999759674
395307064.6610894203
708068847.9481811523
687957763.9839172363
667850017.8797574043
212947011.7810105085
992196...

result:

ok 50000 numbers

Test #59:

score: 40
Accepted
time: 184ms
memory: 154908kb

input:

50000
1 1 1 4 2 6 6 8 5 7 2 3 12 4 11 14 13 1 8 15 7 21 6 23 8 9 23 11 4 18 25 26 25 31 26 24 20 31 35 20 35 31 2 6 6 17 36 22 7 34 42 14 16 18 53 8 25 11 57 49 52 29 63 31 47 58 51 40 39 24 65 58 55 37 36 71 36 59 70 45 51 33 53 45 71 84 43 59 43 43 73 79 63 47 77 70 74 51 67 91 73 56 67 64 73 66 8...

output:

825756550.0094485283
2879203.3629960418
13413400.4445181191
825841427.0235238075
61057.4601928379
2968921.3918093313
3063093.0051699784
704570.2757176929
195439.9734101938
73780.9563638674
3163461.6389359199
1586496.8970775018
13545976.0755272061
1755085.8406883813
825926304.0375990868
458275.269018...

result:

ok 50000 numbers

Test #60:

score: 40
Accepted
time: 191ms
memory: 154648kb

input:

50000
1 1 3 3 3 3 7 4 2 9 9 11 9 13 12 11 17 3 4 16 12 1 17 6 25 17 24 26 1 7 20 3 13 11 25 26 37 26 37 18 5 4 9 32 19 44 38 27 7 10 10 41 53 39 34 36 42 52 16 25 41 33 59 20 25 18 61 26 29 26 45 34 24 67 26 49 65 59 69 39 76 47 41 47 71 63 60 68 61 68 61 66 78 72 89 74 58 76 65 56 88 102 55 94 57 8...

output:

825405121.0242042542
670829.3901956896
825490951.7125949860
825576782.4009857178
1275288.9398229253
3389618.4247939382
444271.4371390569
144446.9192873001
61405004.0094262958
768252.2506610681
64588607.2929858565
1410653.8819401963
1150211.3868545694
213377.9446712809
218751.9087520819
1586161.62095...

result:

ok 50000 numbers

Test #61:

score: 40
Accepted
time: 263ms
memory: 158740kb

input:

50000
1 2 3 2 2 4 3 7 5 3 6 7 11 4 10 7 4 11 12 6 3 17 21 14 3 8 20 6 13 17 6 6 7 23 5 16 34 7 1 20 34 4 26 19 22 16 22 32 44 26 23 14 21 44 29 15 22 24 44 52 42 31 60 33 63 60 41 49 48 60 51 24 40 59 62 69 68 37 56 52 48 63 59 72 47 64 59 74 67 48 64 57 59 92 73 50 94 50 64 70 65 64 67 93 59 59 81 ...

output:

768290519.9460649490
768377304.3087711334
768398761.9808688164
884050369.3786449432
802567482.1920614243
469847441.2497570515
327521563.2487723827
355204.4028047726
226357.9037960387
330457211.2103142738
282058954.9568326473
552128792.2569532394
408873.4959278260
563862801.0342817307
512243271.36178...

result:

ok 50000 numbers

Test #62:

score: 40
Accepted
time: 285ms
memory: 157108kb

input:

50000
1 1 3 4 1 2 1 5 5 3 8 11 5 2 5 3 2 2 16 14 12 21 17 21 18 7 12 20 24 19 25 5 8 1 29 17 36 29 39 23 40 12 33 35 15 40 24 20 13 23 3 6 33 32 18 45 31 54 48 11 47 18 40 44 45 31 44 36 32 33 63 70 60 68 70 69 28 37 58 31 64 42 45 46 42 47 84 48 87 87 48 48 89 89 66 66 83 96 85 74 57 59 60 80 59 62...

output:

753851413.9729552269
668632030.8184285164
887662887.6855792999
715306759.1653084755
782690048.4350833893
886918068.0452108383
249813080.5841712952
714025497.7224979401
233172894.2909970284
922750473.0997104645
774906635.5095171928
845316887.0565385818
472985983.4219114780
656621456.4896187782
408869...

result:

ok 50000 numbers

Test #63:

score: 40
Accepted
time: 223ms
memory: 131580kb

input:

50000
1 1 3 1 4 1 5 1 7 1 9 11 12 5 8 15 1 10 12 17 17 2 3 4 18 21 6 20 18 28 26 28 1 3 32 5 17 32 10 21 40 23 27 14 3 6 16 45 36 21 36 27 51 34 52 21 50 9 10 3 37 42 27 61 36 14 25 32 2 1 25 32 40 71 5 65 30 74 58 31 59 40 40 13 48 77 14 65 53 77 27 52 78 37 26 83 23 78 95 15 92 6 30 34 47 67 50 69...

output:

901951313.1168475151
939637661.0405869484
933802604.7414903641
816014766.8771004677
995460510.2584457397
829205036.3341250420
800648689.4693708420
829926490.9537649155
838950634.1637349129
809656620.2159781456
816265583.2220644951
842745304.2649207115
860895633.8366141319
851045608.6694622040
848187...

result:

ok 50000 numbers

Test #64:

score: 40
Accepted
time: 219ms
memory: 118768kb

input:

50000
1 2 3 1 2 3 1 2 9 5 2 12 3 2 7 15 4 15 8 3 11 15 2 22 9 5 20 7 1 29 10 10 16 19 34 29 7 6 27 18 8 33 8 37 38 7 2 44 40 47 46 50 6 1 42 41 54 39 21 35 44 46 11 18 18 57 24 43 62 63 65 68 16 24 16 43 59 67 67 75 21 8 62 57 44 36 52 26 10 41 30 73 4 88 51 36 20 65 27 92 89 101 45 38 47 39 94 60 5...

output:

633723259.3384447098
643127441.7631225586
626455784.2175383568
629803181.0647768974
623134613.4139747620
656527996.4067044258
626312733.0702204704
632579326.9970593452
626287460.7008609772
629913807.2853693962
623766422.6479620934
628698349.3703250885
560632706.1278438568
527021885.3911910057
620833...

result:

ok 50000 numbers

Test #65:

score: 40
Accepted
time: 208ms
memory: 120360kb

input:

50000
1 1 1 1 5 1 2 1 6 8 7 8 3 4 13 10 14 12 7 17 13 7 9 21 19 1 3 13 7 3 14 7 19 7 18 26 29 2 35 11 30 3 42 25 18 23 18 20 21 15 46 10 35 28 44 55 17 10 26 30 21 21 16 41 13 61 20 53 36 32 68 49 73 46 15 59 75 57 59 37 60 40 75 22 61 10 15 46 80 28 67 24 19 60 34 94 43 43 4 72 29 45 29 46 48 19 37...

output:

651109695.7834606171
613997459.7976236343
641609669.0900797844
618478775.4059352875
613302231.2216587067
614849090.9613227844
633734226.5930724144
614442825.7029399872
655942440.3770165443
621243000.4092745781
562466621.8364591599
630093574.8938322067
620657921.2167444229
612322807.6996889114
624134...

result:

ok 50000 numbers

Test #66:

score: 40
Accepted
time: 231ms
memory: 134264kb

input:

50000
1 1 1 3 1 1 6 2 4 10 2 6 6 11 11 11 6 11 10 20 1 20 5 15 11 24 11 24 4 26 19 23 29 14 24 2 3 21 3 34 30 41 8 33 25 43 14 6 43 19 20 28 33 12 55 29 1 30 3 17 29 25 54 34 22 33 18 57 3 56 42 12 14 61 11 42 35 39 51 20 58 36 28 67 5 23 52 65 59 68 7 61 88 52 74 7 31 66 19 33 82 2 102 87 98 93 90 ...

output:

721192360.2031240463
713888168.6210727692
698074817.9593958855
714616775.7980785370
710842132.8575172424
756738662.9629878998
660494804.7218294144
649845600.4783282280
632481098.5425677299
729587555.2020530701
786801338.4089994431
722544193.5452780724
634891987.2120318413
694150448.1513085365
627762...

result:

ok 50000 numbers

Test #67:

score: 40
Accepted
time: 235ms
memory: 135296kb

input:

50000
1 1 1 1 1 2 3 8 2 5 10 7 7 11 9 8 12 7 6 15 20 11 2 11 23 4 5 3 15 26 23 1 14 23 3 27 6 25 32 20 9 17 16 42 27 8 43 40 8 28 9 17 2 5 20 44 7 58 45 25 36 22 2 61 34 8 14 43 10 50 5 48 3 22 59 57 12 2 36 8 31 62 78 49 64 19 51 64 37 3 1 82 69 48 65 44 97 59 93 60 10 21 65 75 71 31 35 95 56 92 22...

output:

887281894.7965559959
858624458.4543638229
843241691.7461137772
803954601.4838871956
914224147.8824067116
839683532.8751602173
842493057.4084835052
849695205.8387813568
861265659.4710097313
983737945.5729026794
840168953.1017255783
885056018.9442896843
794471740.9281845093
801592350.2045111656
812222...

result:

ok 50000 numbers

Subtask #4:

score: 0
Skipped

Dependency #2:

0%