Submission #658254

#	Time	Username	Problem	Language	Result	Execution time	Memory
658254		Nhoksocqt1	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	27 ms	14036 KiB

kangaroo

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
#define N 2002
#define modl 1000000007
typedef long long ll;
typedef pair<int, int> ii;

int dp[N][N], n, cs, cf;
bool dx[N];

inline void add(int &a, const int &b) {
    if((a += b) >= modl)
        a -= modl;
}

int solve(int id, int last, bool dir) {
    if(id == n - 1) {
        return (dir && last < cf || !dir && last > cf);
    }

    int res(0);
    for (int i = 1; i <= n; ++i) {
        if(!dx[i] && (dir && last < i || !dir && last > i)) {
            dx[i] = 1;
            res += solve(id + 1, i, !dir);
            dx[i] = 0;
        }
    }

    return res;
}

void process(void) {
    cin >> n >> cs >> cf;

    dp[0][0] = 1;
    for (int i = 0; i < n - 1; ++i) {
        for (int group = 0; group <= i; ++group) {
            //cout << dp[i][group] << " \n"[group == i];
            if(!dp[i][group])
                continue;

            if(i + 1 == cs) {
                add(dp[i + 1][group], dp[i][group]);
                if(group > 0) {
                    add(dp[i + 1][group - 1], 1LL * group * dp[i][group] % modl);
                }
            } else
                if(i + 1 == cf) {
                    add(dp[i + 1][group], dp[i][group]);
                    if(group > 0) {
                        add(dp[i + 1][group - 1], 1LL * group * dp[i][group] % modl);
                    }
                } else {
                    add(dp[i + 1][group + 1], dp[i][group]);
                    if(group > 0) {
                        if(i + 1 >= cs) {
                            add(dp[i + 1][group - 1], 1LL * group * dp[i][group] % modl);
                        }

                        if(i + 1 >= cf) {
                            add(dp[i + 1][group - 1], 1LL * group * dp[i][group] % modl);
                        }

                        //add(dp[i + 1][group], 1LL * group * dp[i][group] % modl);
                        if(group > 1)
                            add(dp[i + 1][group - 1], 2LL * group * (group - 1) / 2 % modl * dp[i][group] % modl);
                    }
                }
        }
    }

    //dx[cs] = dx[cf] = 1;
    //cout << solve(1, cs, 0) + solve(1, cs, 1) << '\n';
    cout << dp[n - 1][0];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

 //   freopen("main.inp", "r", stdin);
//..    freopen("main.out", "w", stdout);

    process();
    return 0;
}

Compilation message (stderr)

kangaroo.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
kangaroo.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
kangaroo.cpp: In function 'int solve(int, int, bool)':
kangaroo.cpp:25:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   25 |         return (dir && last < cf || !dir && last > cf);
      |                 ~~~~^~~~~~~~~~~~
kangaroo.cpp:30:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   30 |         if(!dx[i] && (dir && last < i || !dir && last > i)) {
      |                       ~~~~^~~~~~~~~~~

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