oj.uz

Submission #524572

# Submission time Handle Problem Language Result Execution time Memory
524572 2022-02-09T14:41:58 Z sare Ruins 3 (JOI20_ruins3) C++17
100 / 100
 276 ms 11724 KB 
//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) { 
	stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) { 
	string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
	string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
	return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
	bool fst = 1; string res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += to_string(x);
	}
	res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
	return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 1210, MOD = 1e9 + 7;
int dp[MAXN], pre[MAXN][MAXN], comb[MAXN][MAXN];
bool rem[2 * MAXN];

inline int power (ll a, ll b) {
	ll res = 1;
	for (; b; b >>= 1, a = (a * a) % MOD) {
		if (b & 1) {
			res = (res * a) % MOD;
		}
	}
	return res;
}
inline int inv (int x) {
	return power(x, MOD - 2);
}

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

int main() {
	ios::sync_with_stdio(0);
#ifndef LOCAL
	cin.tie(0);
#endif
	for (int i = 0; i < MAXN; i++) {
		comb[i][i] = comb[i][0] = 1;
		for (int j = 1; j < i; j++) {
			comb[i][j] = comb[i - 1][j];
			add(comb[i][j], comb[i - 1][j - 1]);
		}
	}

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		rem[x] = 1;
	}

	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			add(dp[i], 1ll * comb[i - 1][j - 1] * dp[j - 1] % MOD * dp[i - j] % MOD * (i - j + 2) % MOD);
		}
	}
	
	int c0 = 0, c1 = 0;
	pre[n + n + 1][0] = 1;
	for (int k = n + n; k; k--) {
		if (rem[k]) {
			memcpy(pre[k], pre[k + 1], sizeof(pre[k]));
			for (int i = 0; i <= c1 + 1; i++) {
				for (int j = 1; j <= i; j++) {
					add(pre[k][i], 1ll * comb[c1 - j + 1][i - j] * pre[k + 1][j - 1] % MOD * dp[i - j] % MOD * (i - j + 2) % MOD);
				}
			}
			c1++;
		}
		else {
			for (int i = 0; i <= c1; i++) {
				pre[k][i] = 1ll * pre[k + 1][i] * max(0, i - c0) % MOD;
			}
			c0++;
		}
	}
	int ans = 1ll * pre[1][n] * inv(power(2, n)) % MOD;
	cout << ans << '\n';
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5964 KB Output is correct
2 Correct 3 ms 5964 KB Output is correct
3 Correct 3 ms 5964 KB Output is correct
4 Correct 3 ms 5964 KB Output is correct
5 Correct 3 ms 5964 KB Output is correct
6 Correct 3 ms 5964 KB Output is correct
7 Correct 4 ms 5964 KB Output is correct
8 Correct 3 ms 5964 KB Output is correct
9 Correct 3 ms 5964 KB Output is correct
10 Correct 3 ms 5964 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5964 KB Output is correct
2 Correct 3 ms 5964 KB Output is correct
3 Correct 3 ms 5964 KB Output is correct
4 Correct 3 ms 5964 KB Output is correct
5 Correct 3 ms 5964 KB Output is correct
6 Correct 3 ms 5964 KB Output is correct
7 Correct 4 ms 5964 KB Output is correct
8 Correct 3 ms 5964 KB Output is correct
9 Correct 3 ms 5964 KB Output is correct
10 Correct 3 ms 5964 KB Output is correct
11 Correct 4 ms 6476 KB Output is correct
12 Correct 4 ms 6476 KB Output is correct
13 Correct 4 ms 6476 KB Output is correct
14 Correct 4 ms 6476 KB Output is correct
15 Correct 4 ms 6464 KB Output is correct
16 Correct 4 ms 6476 KB Output is correct
17 Correct 4 ms 6476 KB Output is correct
18 Correct 4 ms 6476 KB Output is correct
19 Correct 4 ms 6476 KB Output is correct
20 Correct 3 ms 6476 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5964 KB Output is correct
2 Correct 3 ms 5964 KB Output is correct
3 Correct 3 ms 5964 KB Output is correct
4 Correct 3 ms 5964 KB Output is correct
5 Correct 3 ms 5964 KB Output is correct
6 Correct 3 ms 5964 KB Output is correct
7 Correct 4 ms 5964 KB Output is correct
8 Correct 3 ms 5964 KB Output is correct
9 Correct 3 ms 5964 KB Output is correct
10 Correct 3 ms 5964 KB Output is correct
11 Correct 4 ms 6476 KB Output is correct
12 Correct 4 ms 6476 KB Output is correct
13 Correct 4 ms 6476 KB Output is correct
14 Correct 4 ms 6476 KB Output is correct
15 Correct 4 ms 6464 KB Output is correct
16 Correct 4 ms 6476 KB Output is correct
17 Correct 4 ms 6476 KB Output is correct
18 Correct 4 ms 6476 KB Output is correct
19 Correct 4 ms 6476 KB Output is correct
20 Correct 3 ms 6476 KB Output is correct
21 Correct 269 ms 11616 KB Output is correct
22 Correct 261 ms 11544 KB Output is correct
23 Correct 256 ms 11500 KB Output is correct
24 Correct 265 ms 11556 KB Output is correct
25 Correct 258 ms 11500 KB Output is correct
26 Correct 266 ms 11548 KB Output is correct
27 Correct 266 ms 11568 KB Output is correct
28 Correct 260 ms 11520 KB Output is correct
29 Correct 261 ms 11180 KB Output is correct
30 Correct 265 ms 11620 KB Output is correct
31 Correct 255 ms 11556 KB Output is correct
32 Correct 264 ms 11596 KB Output is correct
33 Correct 257 ms 11568 KB Output is correct
34 Correct 276 ms 11724 KB Output is correct
35 Correct 268 ms 11596 KB Output is correct
36 Correct 261 ms 11592 KB Output is correct