Submission #1242386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242386		muhammad-mutahir	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	52 ms	55112 KiB

kangaroo

#ifdef AVX2
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#endif
 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define print(l) for(auto i:l)cout<<i<<" ";cout<<endl;
#define se second
#define fi first
#define input(t,l,n) vector<t>l(n);for(int i = 0;i<n;i++)cin>>l[i];
#define pb push_back
#define all(l) l.begin(),l.end() 
#define endl '\n'
 

const int M = 1e9+7;
const int inf = 1e18;
 
 
 
void io(){
    
    #ifndef ONLINE_JUDGE
    freopen("inp.in","r",stdin);
    freopen("out.in","w",stdout);
    #endif
}


void fastio(){
    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);
    cout << fixed<<setprecision(9);
    srand(time(0));
}

vector<vector<vector<int>>>adj;
vector<int>vis,ch,dis;
int n,m,q;
const int N =1e5+10;
const int lg = 20; 
int sp[N][lg];
int sp1[N][lg];
void buildsp(){
    for(int i = 1;i<lg;i++){
        for(int j = 1;j<=m;j++){
            sp[j][i] = sp[sp[j][i-1]][i-1];
            sp1[j][i] = max(sp1[j][i-1],sp1[sp[j][i-1]][i-1]);
        }
    }
}



int kp(int c,int p){
    for(int i = lg-1;i>=0;i--){
        if((p&(1<<i))){
            c = sp[c][i];
        }
    }
    return c;
}
 
void dfs(int c){
 
    for(auto f:adj[c]){
        int i = f[0];
        if(!vis[i]){
            dis[i] = dis[c]+1;
            sp[i][0] = c;
            sp1[i][0] = f[1];
 
            vis[i] = 1;
            dfs(i);
        }
    }
}
 
int lca(int u,int v){
    if(dis[u] > dis[v] ){
        swap(u,v);
    }
    v = kp(v,dis[v]-dis[u]);
    
    if(v == u){
        return u;
    }
    // cout<<u<<" "<<v<<"<<<<<<<<<<"<<endl;
    for(int i = lg-1;i>=0;i--){
        if(sp[u][i]!= sp[v][i]){
            u = sp[u][i];
            v = sp[v][i];
        }
    }
    return sp[u][0];
}
int dp[2000+10][2000+10][3];
void solve(){
    int f,s;
    cin>>n>>s>>f;
    if(s == 1 or f == 1){
        dp[1][1][1] = 1;
    }
    else{
        dp[1][1][0] = 1;
    }
    // dp[1][1] = 1;
    for(int i = 1;i<n;i++){
        for(int j = 1;j<=i;j++){
            if(i+1 == s or i+1 == f){
                for(int k = 0;k<2;k++){
                    dp[i+1][j+1][k+1] += dp[i][j][k];
                    dp[i+1][j][k+1] += dp[i][j][k];
                    dp[i+1][j+1][k+1] %=M;
                    dp[i+1][j][k+1] %=M;
                }
            }
            else{
                for(int k = 0;k<3;k++){
                    dp[i+1][j+1][k] += (dp[i][j][k]*(j+1-k))%M;
                    dp[i+1][j-1][k] += (dp[i][j][k]*(j-1))%M;
                    dp[i+1][j+1][k] %=M;
                    dp[i+1][j-1][k] %=M;
                }
            }

        }
    }
    cout<<dp[n][1][2]<<endl;


}   



 
signed main(){
    // io();
    fastio();
    int t = 1;
    // cin>>t;
    while(t--)solve();
}  

Compilation message (stderr)

kangaroo.cpp: In function 'void io()':
kangaroo.cpp:28:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     freopen("inp.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
kangaroo.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     freopen("out.in","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49