提出 #19644174


ソースコード 拡げる

//clear adj and visited vector declared globally after each test case
//check for long long overflow
//while adding and subs check if mod becomes -ve
//while using an integer directly in a builtin function add ll
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Dont keep array name as size or any other key word
//Incase of close mle change language to c++17 or c++14 
/**#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops”)**/
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007ll //998244353ll
#define lld long double
#define mii map<int, int>
#define mci map<char, int>
#define msi map<string, int>
#define pii pair<int, int>
#define ff first
#define ss second 
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)    
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=100005, INF=2000000000000000000;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
    int g=__gcd(a, b);
    return a/g*b;
}
int power(int a, int b, int p)
    {
        if(a==0)
        return 0;
        int res=1;
        a%=p;
        while(b>0)
        {
            if(b&1)
            res=(res*a)%p;
            b>>=1;
            a=(a*a)%p;
        }
        return res;
    }
lld dp[N], suf[N], n, m, dp2[N], inv, ans=0.0;
void fun(int pos)
{
    if(pos==n)
    return;
    fun(pos+1);
    int rg=min(n, pos+m+1);
    if(suf[pos]==suf[pos+1])
    {
        dp[pos]=((((dp[pos+1]-dp[rg]))/m)+1.0);
        dp2[pos]=((dp2[pos+1]-dp2[rg]+suf[pos+1]-suf[rg])/m);
    }
    if(pos==0)
    {
        dp2[pos]=(1.0-dp2[pos]);
        if(dp2[pos]==0)
        ans=-1;
        else
        ans=(dp[pos]/dp2[pos]);
    }
    dp[pos]=(dp[pos]+dp[pos+1]);
    dp2[pos]=(dp2[pos]+dp2[pos+1]);
}
int32_t main()
{
    IOS;
    int k;
    cin>>n>>m>>k;
    inv=power(m, mod-2, mod);
    rep(i,0,N)
    {
        dp[i]=dp2[i]=suf[i]=0.0;
    }
    rep(i,0,k)
    {
        int a;
        cin>>a;
        suf[a]+=1.0;
    }
    for(int i=n-1;i>=0;i--)
    suf[i]+=suf[i+1];
    fun(0);
    lld eps=1e-9;
    if(ans<=eps)
    cout<<-1;
    else
    cout<<ans;
}

提出情報

提出日時
問題 F - Sugoroku2
ユーザ yash_daga
言語 C++ (GCC 9.2.1)
得点 600
コード長 2922 Byte
結果 AC
実行時間 20 ms
メモリ 14680 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 600 / 600
結果
AC × 4
AC × 30
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All hand_01.txt, hand_02.txt, hand_04.txt, max_01.txt, max_02.txt, max_03.txt, max_04.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_14.txt, random_15.txt, random_16.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, unreachable_01.txt, unreachable_02.txt, unreachable_03.txt, unreachable_04.txt
ケース名 結果 実行時間 メモリ
hand_01.txt AC 16 ms 14564 KiB
hand_02.txt AC 15 ms 14552 KiB
hand_04.txt AC 6 ms 8388 KiB
max_01.txt AC 15 ms 14612 KiB
max_02.txt AC 15 ms 14604 KiB
max_03.txt AC 19 ms 14660 KiB
max_04.txt AC 14 ms 14544 KiB
random_01.txt AC 19 ms 14680 KiB
random_02.txt AC 8 ms 9292 KiB
random_03.txt AC 15 ms 14616 KiB
random_04.txt AC 9 ms 8532 KiB
random_05.txt AC 15 ms 14552 KiB
random_06.txt AC 14 ms 14296 KiB
random_07.txt AC 16 ms 14544 KiB
random_08.txt AC 8 ms 8668 KiB
random_09.txt AC 17 ms 14604 KiB
random_10.txt AC 13 ms 10812 KiB
random_11.txt AC 15 ms 14612 KiB
random_12.txt AC 20 ms 14552 KiB
random_14.txt AC 13 ms 12040 KiB
random_15.txt AC 15 ms 14612 KiB
random_16.txt AC 10 ms 11224 KiB
sample_01.txt AC 10 ms 8292 KiB
sample_02.txt AC 7 ms 8400 KiB
sample_03.txt AC 11 ms 8300 KiB
sample_04.txt AC 14 ms 14612 KiB
unreachable_01.txt AC 9 ms 10020 KiB
unreachable_02.txt AC 12 ms 11420 KiB
unreachable_03.txt AC 9 ms 10428 KiB
unreachable_04.txt AC 13 ms 12452 KiB