oj.uz

Submission #1009993

# Submission time Handle Problem Language Result Execution time Memory
1009993 2024-06-28T08:53:33 Z modwwe Ruins 3 (JOI20_ruins3) C++17
100 / 100
 1079 ms 5148 KB 
//https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=1e18;
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    int a,b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e,f;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
///     fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo(),down
}
bool a[1201];
int dp[601][601][2];
int dp2[601];
int ipow(int x, int p)
{
    int  ret = 1, piv = x;
    while(p)
    {
        if(p&1) ret *= piv;
        piv *= piv;
        ret %= mod2;
        piv %= mod2;
        p >>= 1;
    }
    return ret;
}
void phongbeo()
{
    cin>>n;
    k=ipow(2,mod2-2);
    for(int i=1; i<=n; i++)
    {
        cin>>l;
        a[l]=1;
    }
//  check();/// in 0 ra
    dp2[0]=1;
    for(int i=n*2; i>=1; --i)
    {
        if(!a[i])
        {
            for(int j=s7+1; j<=s3; j++)
                dp2[j]=(dp2[j]*(j-s7))%mod2;
            dp2[s7]=0;
            s7++;
        }
        else
        {
            s4=s3;
            s3++;
            for(int j=s7; j<=s3-1; j++)
                dp[j][j][0]=dp2[j];
            for(int j=0; j<=s3; j++)
                for(int z=0; z<=j; z++)
                    for(int f=0; f<=1; f++)
                        if(dp[j][z][f]!=0)
                        {
                            if(j!=s3){
                            dp[j+1][z][f]=(dp[j+1][z][f]+dp[j][z][f])%mod2;
                            if(f==0)
                            {
                                if(j!=z)dp[j+1][z+1][f]=((dp[j][z][f]*(s4-z))%mod2+dp[j+1][z+1][f])%mod2;
                                if(z+1<j&&s4-z>=2)dp[j+1][z+2][f]=(((((((dp[j][z][f]*(s4-z))%mod2)*(s4-z-1))%mod2)*k)%mod2*k)%mod2+dp[j+1][z+2][f])%mod2;
                                dp[j+1][z+1][1-f]=(dp[j+1][z+1][1-f]+dp[j][z][f])%mod2;
                                if(z+2<=j+1&&s4>z){dp[j+1][z+2][1-f]=((((dp[j][z][f]*k)%mod2)*(s4-z))%mod2+dp[j+1][z+2][1-f])%mod2;
                                }
                            }
                            if(f==1&&s3>=z)
                                dp[j+1][z+1][f]=((dp[j][z][f]*(s3-z))%mod2+dp[j+1][z+1][f])%mod2;
                            if(f==1&&s3-z>=2)
                                dp[j+1][z+2][f]=(((((((dp[j][z][f]*(s3-z))%mod2)*(s3-z-1))%mod2)*k)%mod2*k)%mod2+dp[j+1][z+2][f])%mod2;}
                            if(j!=z||f!=1)
                                dp[j][z][f]=0;
                        }
            for(int j=s7; j<=s3; j++)
            {
                                dp2[j]=(dp2[j]+dp[j][j][1])%mod2,dp[j][j][1]=0;

            }
        }

    }// 1 2
    cout<<dp2[n]%mod2;
}

Compilation message

ruins3.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main()
      | ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 0 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 0 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 55 ms 2900 KB Output is correct
22 Correct 63 ms 2896 KB Output is correct
23 Correct 56 ms 2900 KB Output is correct
24 Correct 61 ms 3164 KB Output is correct
25 Correct 49 ms 596 KB Output is correct
26 Correct 54 ms 2724 KB Output is correct
27 Correct 46 ms 1872 KB Output is correct
28 Correct 51 ms 2640 KB Output is correct
29 Correct 50 ms 348 KB Output is correct
30 Correct 1079 ms 5148 KB Output is correct
31 Correct 566 ms 4952 KB Output is correct
32 Correct 786 ms 4944 KB Output is correct
33 Correct 1022 ms 5080 KB Output is correct
34 Correct 548 ms 4756 KB Output is correct
35 Correct 783 ms 4944 KB Output is correct
36 Correct 1010 ms 4948 KB Output is correct