Submission #1109947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109947		InvMOD	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	1 ms	336 KiB

kangaroo

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

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 2e3+5;
const int MOD = 1e9+7;


int n, start_point, end_point;

namespace Subtask1{

    const int N = 10;

    bool vis[N]; int answer;
    vector<int> vec;

    void backtrack(int pos = 0){
        if(pos == n){
            for(int i = 1; i < sz(vec)-1; i++){
                if(vec[i-1] < vec[i] && vec[i] < vec[i+1]) return;
                if(vec[i-1] > vec[i] && vec[i] > vec[i+1]) return;
            }
            answer += (vec[0] == start_point && vec.back() == end_point);
            return;
        }

        for(int i = 1; i <= n; i++){
            if(vis[i]) continue;
            vis[i] = true;
            vec.push_back(i);
            backtrack(pos+1);
            vec.pop_back();
            vis[i] = false;
        }
        return;
    }


    void process()
    {
        answer = 0;
        backtrack();
        cout << answer <<"\n";
        return;
    }
}

namespace Subtask3{

    int dp[N][N];

    int mul(int x, int y){return (1ll * x * y) % MOD;}
    int add(int x, int y){return x + y < MOD ? x + y : x + y - MOD;}

    void process()
    {
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++){
            if(i == start_point || i == end_point){
                // add component i to the first or i to the first component, only 1 smaller value in the first one (for start point)
                // add component i to the last or i to the last component, only 1 smaller value in the last one (for end point)
                for(int j = 1; j <= i; j++){
                    dp[i][j] = add(dp[i][j], add(dp[i-1][j], dp[i-1][j-1]));
                    //cout << dbg(i) << dbg(j) << dbg(dp[i][j]) <<"\n";
                }
            }
            else{
                for(int j = 1; j <= i; j++){
                    int place_point = (j > 1 ? j - (i > start_point) - (i > end_point) : 1);

                    // Place new component at place point
                    dp[i][j] = add(dp[i][j], mul(dp[i-1][j-1], place_point));

                    // Merge 2 component
                    if(j+1 < i) dp[i][j] = add(dp[i][j], mul(j, dp[i-1][j+1]));

                    //cout << dbg(i) << dbg(j) << dbg(dp[i][j]) <<"\n";
                    // We don't add any elements to any component
                }
            }
        }

        cout << dp[n][1] <<"\n";
    }
}

void solve()
{
    cin >> n >> start_point >> end_point;

    Subtask1::process();
    Subtask3::process();
}

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

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
kangaroo.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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