oj.uz

Submission #964071

# Submission time Handle Problem Language Result Execution time Memory
964071 2024-04-16T09:23:27 Z LucaIlie Kangaroo (CEOI16_kangaroo) C++17
6 / 100
 4 ms 26972 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200;
const int MOD = 1e9 + 7;

struct ZP {
    int x;

    ZP operator + ( ZP a ) {
        return { x + a.x };
    }

    void operator += ( ZP a ) {
        x += a.x;
    }

    ZP operator * ( ZP a ) {
        return { (int)((long long)x * a.x % MOD) };
    }

    ZP operator * ( int a ) {
        return { (int)((long long)x * a % MOD) };
    }

    void operator = ( int a ) {
        x = a;
    }

    void out() {
        cout << x << "\n";
    }
};


ZP dp[MAX_N + 1][MAX_N + 1][MAX_N + 1][2][2];

void afis( int n, int i ) {
    for ( int mn = 0; mn <= n; mn++ ) {
        for ( int mx = 0; mx <= n; mx++ )
            printf( "%d: %d %d -- %d %d %d %d\n", i, mn, mx, dp[i][mn][mx][0][0], dp[i][mn][mx][0][1], dp[i][mn][mx][1][0], dp[i][mn][mx][1][1] );
    }
}

int main() {
    int n, s, f;

    cin >> n >> s >> f;
    if ( s > f )
        swap( s, f );

    if ( s == 1 ) {
        if ( f == 2 )
            dp[3][0][1][1][1] = 1;
        dp[2][0][0][1][0] = 1;
    } else
        dp[1][1][0][0][0] = 1;

    int p = 2;
    for ( int i = 0; i < s - 1; i++ ) {
        for ( int mn = 0; mn <= n; mn++ ) {
            for ( int mx = 0; mx <= n; mx++ ) {
                dp[i + 1][mn][mx][0][0] += dp[i][mn][mx][0][0] * (mx * 2 + 2);
                dp[i + 1][mn + 1][mx + 1][0][0] += dp[i][mn][mx][0][0] * (p - 2 - mx * 2);
            }
        }
        if ( i == 0 && s > 1 )
            p--;
        p++;
    }
    for ( int mn = 0; mn <= n; mn++ ) {
        for ( int mx = 0; mx <= n; mx++ ) {
            dp[s][mn][mx][0][0] = dp[s - 1][mn][mx][0][0];
            dp[s][mn][mx][0][1] = dp[s - 1][mn][mx][0][1];
            dp[s][mn][mx][1][0] = dp[s - 1][mn][mx][1][0];
            dp[s][mn][mx][1][1] = dp[s - 1][mn][mx][1][1];
        }
    }

    for ( int i = s; i < f - 1; i++ ) {
        for ( int mn = 0; mn <= n; mn++ ) {
            for ( int mx = 0; mx <= n; mx++ ) {
                dp[i + 1][mn][mx][0][0] += dp[i][mn][mx][0][0] * (mx * 2 + 1);
                dp[i + 1][mn + 1][mx + 1][0][0] += dp[i][mn][mx][0][0] * (p - 2 - mx * 2);
                dp[i + 1][mn][mx + 1][1][0] += dp[i][mn][mx][0][0];

                dp[i + 1][mn][mx][1][0] += dp[i][mn][mx][1][0] * (mx * 2 + 1);
                dp[i + 1][mn + 1][mx + 1][1][0] += dp[i][mn][mx][1][0] * (p - 1 - mx * 2);
            }
        }
        if ( s == 1 && i == s )
            p--;
        p++;
    }
    for ( int mn = 0; mn <= n; mn++ ) {
        for ( int mx = 0; mx <= n; mx++ ) {
            dp[f][mn][mx][0][0] = dp[f - 1][mn][mx][0][0];
            dp[f][mn][mx][0][1] = dp[f - 1][mn][mx][0][1];
            dp[f][mn][mx][1][0] = dp[f - 1][mn][mx][1][0];
            dp[f][mn][mx][1][1] = dp[f - 1][mn][mx][1][1];
        }
    }

    for ( int i = f; i < n; i++ ) {
        for ( int mn = 0; mn <= n; mn++ ) {
            for ( int mx = 0; mx <= n; mx++ ) {
                dp[i + 1][mn][mx][0][0] += dp[i][mn][mx][0][0] * mx * 2;
                dp[i + 1][mn + 1][mx + 1][0][0] += dp[i][mn][mx][0][0] * (p - 2 - mx * 2);
                dp[i + 1][mn][mx + 1][1][0] += dp[i][mn][mx][0][0];
                dp[i + 1][mn][mx + 1][0][1] += dp[i][mn][mx][0][0];

                dp[i + 1][mn][mx][1][0] += dp[i][mn][mx][1][0] * mx * 2;
                dp[i + 1][mn + 1][mx + 1][1][0] += dp[i][mn][mx][1][0] * (p - 1 - mx * 2);
                dp[i + 1][mn][mx + 1][1][1] += dp[i][mn][mx][1][0];

                dp[i + 1][mn][mx][0][1] += dp[i][mn][mx][0][1] * mx * 2;
                dp[i + 1][mn + 1][mx + 1][0][1] += dp[i][mn][mx][0][1] * (p - 1 - mx * 2);
                dp[i + 1][mn][mx + 1][1][1] += dp[i][mn][mx][0][1];

                dp[i + 1][mn][mn][1][1] += dp[i][mn][mx][1][1] * mx * 2;
                dp[i + 1][mn + 1][mx + 1][1][1] += dp[i][mn][mx][1][1] * (p - mx * 2);
            }
        }
        if ( f == 2 && i == f )
            p--;
        p++;
    }

    ZP ans;
    ans = 0;
    for ( int i = 0; i < 2; i++ ) {
        for ( int j = 0; j < 2; j++ ) {
            if ( n % 2 == 0 )
                ans += dp[n][(n - 2) / 2][(n - 2) / 2][i][j];
            else
                ans += dp[n][(n - 2) / 2][n - 2 - (n - 2) / 2][i][j] + dp[n][n - 2 - (n - 2) / 2][(n - 2) / 2][i][j];
        }
    }

    ans.out();

    return 0;
}

Compilation message

kangaroo.cpp: In function 'void afis(int, int)':
kangaroo.cpp:42:36: warning: format '%d' expects argument of type 'int', but argument 5 has type 'ZP' [-Wformat=]
   42 |             printf( "%d: %d %d -- %d %d %d %d\n", i, mn, mx, dp[i][mn][mx][0][0], dp[i][mn][mx][0][1], dp[i][mn][mx][1][0], dp[i][mn][mx][1][1] );
      |                                   ~^                         ~~~~~~~~~~~~~~~~~~~
      |                                    |                                           |
      |                                    int                                         ZP
kangaroo.cpp:42:39: warning: format '%d' expects argument of type 'int', but argument 6 has type 'ZP' [-Wformat=]
   42 |             printf( "%d: %d %d -- %d %d %d %d\n", i, mn, mx, dp[i][mn][mx][0][0], dp[i][mn][mx][0][1], dp[i][mn][mx][1][0], dp[i][mn][mx][1][1] );
      |                                      ~^                                           ~~~~~~~~~~~~~~~~~~~
      |                                       |                                                             |
      |                                       int                                                           ZP
kangaroo.cpp:42:42: warning: format '%d' expects argument of type 'int', but argument 7 has type 'ZP' [-Wformat=]
   42 |             printf( "%d: %d %d -- %d %d %d %d\n", i, mn, mx, dp[i][mn][mx][0][0], dp[i][mn][mx][0][1], dp[i][mn][mx][1][0], dp[i][mn][mx][1][1] );
      |                                         ~^                                                             ~~~~~~~~~~~~~~~~~~~
      |                                          |                                                                               |
      |                                          int                                                                             ZP
kangaroo.cpp:42:45: warning: format '%d' expects argument of type 'int', but argument 8 has type 'ZP' [-Wformat=]
   42 |             printf( "%d: %d %d -- %d %d %d %d\n", i, mn, mx, dp[i][mn][mx][0][0], dp[i][mn][mx][0][1], dp[i][mn][mx][1][0], dp[i][mn][mx][1][1] );
      |                                            ~^                                                                               ~~~~~~~~~~~~~~~~~~~
      |                                             |                                                                                                 |
      |                                             int                                                                                               ZP

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Incorrect 4 ms 26972 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Incorrect 4 ms 26972 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Incorrect 4 ms 26972 KB Output isn't correct
5 Halted 0 ms 0 KB -