oj.uz

Submission #445180

# Submission time Handle Problem Language Result Execution time Memory
445180 2021-07-16T18:44:41 Z KYoA_A Kangaroo (CEOI16_kangaroo) C++17
100 / 100
 19 ms 16060 KB 
/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

// #define kyoa_a
#define rep(i, a, b)	for(int i = a; i < (b); ++i)
#define rrep(a, b, c)	for(int a = (b); a > c; --a)
#define each(a, b)	for(auto& a : b)

#define sz(x)       (int)(x).size()
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(), (a).rend()

#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define vt vector
#define ar array
#define pii pair<int, int>
#define vi vector<int>
#define pll pair<ll, ll>
#define pct(x) __builtin_popcount(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define rsz resize
#define bk back()

constexpr int log2(int x) { return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x))
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <class T> bool umin(T& a, const T& b){return b<a?a=b, 1:0;}
template <class T> bool umax(T& a, const T& b){return a<b?a=b, 1:0;}

using ll = long long;
using ld = long double;
using str = string;

const int inf = (int)1e9 + 5;
const ll infl = (ll)1e18 + 5;
const int mod = 1e9 + 7;
const int N = 2005;

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define dbg(x...) cerr <<" [" << #x << "] = ["; _print(x);
#else
#define dbg(x...)
#endif

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/

const int MOD=1000000007;
struct Mint {
    int val;
 
    Mint(long long v = 0) {
        if (v < 0)
            v = v % MOD + MOD;
        if (v >= MOD)
            v %= MOD;
        val = v;
    }
 
    static int mod_inv(int a, int m = MOD) {
        int g = m, r = a, x = 0, y = 1;
        while (r != 0) {
            int q = g / r;
            g %= r; swap(g, r);
            x -= q * y; swap(x, y);
        } 
        return x < 0 ? x + m : x;
    } 
    explicit operator int() const {
        return val;
    }
    Mint& operator+=(const Mint &other) {
        val += other.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    Mint& operator-=(const Mint &other) {
        val -= other.val;
        if (val < 0) val += MOD;
        return *this;
    }
    static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
           #if !defined(_WIN32) || defined(_WIN64)
                return x % m;
           #endif
           unsigned x_high = x >> 32, x_low = (unsigned) x;
           unsigned quot, rem;
           asm("divl %4\n"
            : "=a" (quot), "=d" (rem)
            : "d" (x_high), "a" (x_low), "r" (m));
           return rem;
    }
    Mint& operator*=(const Mint &other) {
        val = fast_mod((uint64_t) val * other.val);
        return *this;
    }
    Mint& operator/=(const Mint &other) {
        return *this *= other.inv();
    }
    friend Mint operator+(const Mint &a, const Mint &b) { return Mint(a) += b; }
    friend Mint operator-(const Mint &a, const Mint &b) { return Mint(a) -= b; }
    friend Mint operator*(const Mint &a, const Mint &b) { return Mint(a) *= b; }
    friend Mint operator/(const Mint &a, const Mint &b) { return Mint(a) /= b; }
    Mint& operator++() {
        val = val == MOD - 1 ? 0 : val + 1;
        return *this;
    }
    Mint& operator--() {
        val = val == 0 ? MOD - 1 : val - 1;
        return *this;
    }
    Mint operator++(int32_t) { Mint before = *this; ++*this; return before; }
    Mint operator--(int32_t) { Mint before = *this; --*this; return before; }
    Mint operator-() const {
        return val == 0 ? 0 : MOD - val;
    }
    bool operator==(const Mint &other) const { return val == other.val; }
    bool operator!=(const Mint &other) const { return val != other.val; }
    Mint inv() const {
        return mod_inv(val);
    }
    Mint power(long long p) const {
        assert(p >= 0);
        Mint a = *this, result = 1;
        while (p > 0) {
            if (p & 1)
                result *= a;
 
            a *= a;
            p >>= 1;
        }
        return result;
    }
    friend ostream& operator << (ostream &stream, const Mint &m) {
        return stream << m.val;
    }
    friend istream& operator >> (istream &stream, Mint &m) {
        return stream>>m.val;   
    }
};


int n, s, e;
Mint dp[N][N];

void solve(){
	cin >> n >> s >> e;

	dp[1][1] = 1;

	rep(i, 1, n){
		rep(j, 1, i+1){
			if(i+1 == s || i+1 == e){
				dp[i+1][j+1] += dp[i][j];
				dp[i+1][j] += dp[i][j];
			}else{
				dp[i+1][j+1] += dp[i][j]*(j - 1 + (i+1 < s) + (i+1 < e));
				dp[i+1][j-1] += dp[i][j]*(j-1);
			}
		}
	}
	cout << dp[n][1] << '\n';

}

int main(){
	#ifdef kyoa_a
		auto begin = std::chrono::high_resolution_clock::now();
	#endif

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	solve();

	#ifdef kyoa_a
		auto end = std::chrono::high_resolution_clock::now();
		cout << setprecision(3) << fixed;
		cout << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
	#endif
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15948 KB Output is correct
2 Correct 8 ms 16024 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15948 KB Output is correct
2 Correct 8 ms 16024 KB Output is correct
3 Correct 8 ms 15948 KB Output is correct
4 Correct 8 ms 15944 KB Output is correct
5 Correct 8 ms 16056 KB Output is correct
6 Correct 8 ms 16060 KB Output is correct
7 Correct 8 ms 16052 KB Output is correct
8 Correct 8 ms 16056 KB Output is correct
9 Correct 8 ms 15948 KB Output is correct
10 Correct 8 ms 15956 KB Output is correct
11 Correct 8 ms 16036 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15948 KB Output is correct
2 Correct 8 ms 16024 KB Output is correct
3 Correct 8 ms 15948 KB Output is correct
4 Correct 8 ms 15944 KB Output is correct
5 Correct 8 ms 16056 KB Output is correct
6 Correct 8 ms 16060 KB Output is correct
7 Correct 8 ms 16052 KB Output is correct
8 Correct 8 ms 16056 KB Output is correct
9 Correct 8 ms 15948 KB Output is correct
10 Correct 8 ms 15956 KB Output is correct
11 Correct 8 ms 16036 KB Output is correct
12 Correct 8 ms 15928 KB Output is correct
13 Correct 8 ms 15948 KB Output is correct
14 Correct 7 ms 16016 KB Output is correct
15 Correct 7 ms 15948 KB Output is correct
16 Correct 7 ms 15976 KB Output is correct
17 Correct 8 ms 16020 KB Output is correct
18 Correct 9 ms 15948 KB Output is correct
19 Correct 8 ms 15960 KB Output is correct
20 Correct 8 ms 15948 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15948 KB Output is correct
2 Correct 8 ms 16024 KB Output is correct
3 Correct 8 ms 15948 KB Output is correct
4 Correct 8 ms 15944 KB Output is correct
5 Correct 8 ms 16056 KB Output is correct
6 Correct 8 ms 16060 KB Output is correct
7 Correct 8 ms 16052 KB Output is correct
8 Correct 8 ms 16056 KB Output is correct
9 Correct 8 ms 15948 KB Output is correct
10 Correct 8 ms 15956 KB Output is correct
11 Correct 8 ms 16036 KB Output is correct
12 Correct 8 ms 15928 KB Output is correct
13 Correct 8 ms 15948 KB Output is correct
14 Correct 7 ms 16016 KB Output is correct
15 Correct 7 ms 15948 KB Output is correct
16 Correct 7 ms 15976 KB Output is correct
17 Correct 8 ms 16020 KB Output is correct
18 Correct 9 ms 15948 KB Output is correct
19 Correct 8 ms 15960 KB Output is correct
20 Correct 8 ms 15948 KB Output is correct
21 Correct 9 ms 15948 KB Output is correct
22 Correct 9 ms 16052 KB Output is correct
23 Correct 9 ms 15948 KB Output is correct
24 Correct 19 ms 15948 KB Output is correct
25 Correct 19 ms 15948 KB Output is correct
26 Correct 19 ms 16048 KB Output is correct
27 Correct 18 ms 16056 KB Output is correct
28 Correct 14 ms 16032 KB Output is correct