oj.uz

Submission #212562

# Submission time Handle Problem Language Result Execution time Memory
212562 2020-03-23T14:24:25 Z egorlifar Ruins 3 (JOI20_ruins3) C++17
100 / 100
 219 ms 11648 KB 
/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
       
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define rank rank228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
using ll = long long;
using ld = long double;
// const int MAXMEM = 200 * 1000 * 1024;
// char _memory[MAXMEM];
// size_t _ptr = 0;
// void* operator new(size_t _x) { _ptr += _x; return _memory + _ptr - _x; }
// void operator delete (void*) noexcept {}
const string FILENAME = "input";
const int MAXN = 1205;
const int Mod = 1000000007;


int sum(int a, int b){
 	return (a + b >= Mod ? a + b - Mod: a + b);
}


int mul(int a, int b) {
	return ((ll)a * b) % Mod;
}


int powm(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = mul(res, a);
        }
        b >>= 1;
        a = mul(a, a);
    }
    return res;
}

int n;
int a[MAXN];
bool survived[MAXN];
int c[MAXN][MAXN];
int fact[MAXN];
int pr[MAXN][MAXN];
int ways[MAXN];
int dp[2][MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  //  read(FILENAME); 
    cin >> n;
    for (int i = 0; i < n; i++) {
    	cin >> a[i];
        survived[a[i]] = true;
    }
    for (int i = 0; i <= 2 * n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) {
                c[i][j] = 1;
            } else {
                c[i][j] = sum(c[i - 1][j], c[i - 1][j - 1]);
            }
        }
    }
    fact[0] = 1;
    for (int i = 1; i <= 2 * n; i++) {
        fact[i] = mul(fact[i - 1], i);
    }
    pr[0][0] = 1;
    for (int i = 0; i <= 2 * n; i++) {
        for (int j = i; j <= 2 * n + 1; j++) {
            if (j + 2 <= 2 * n) {
                pr[i + 1][j + 2] = sum(pr[i + 1][j + 2], pr[i][j]);
            }
            if (j + 1 <= 2 * n) {
                pr[i + 1][j + 1] = sum(pr[i + 1][j + 1], sum(pr[i][j], pr[i][j]));
            }
            pr[i + 1][j] = sum(pr[i + 1][j], pr[i][j]);
        }
    }
   // cout << pr[1][1] << endl;
    for (int i = 1; i <= 2 * n + 1; i++) {
        ways[i] = pr[i - 1][i - 1];
        ways[i] = mul(ways[i], mul(fact[i - 1], i + 1));
    }
    dp[0][0] = 1;
  //  cout << c[0][0] << endl;
    int cnt1 = 0, cnt0 = 0;
    for (int i = 2 * n; i >= 1; i--) {
        for (int j = cnt0; j <= cnt1 + 1; j++) {
            if (dp[0][j] != 0) {
                if (survived[i]) {
                    dp[1][j] = sum(dp[1][j], dp[0][j]);
                    for (int k = j + 1; k <= cnt1 + 2; k++) {
                        int val = mul(mul(dp[0][j], c[cnt1 - j][k - j - 1]), ways[k - j]);
                        dp[1][k] = sum(dp[1][k], val);
                    }
                } else {
                    dp[1][j] = sum(dp[1][j], mul(dp[0][j], j - cnt0));
                }
            }
        }
        if (survived[i]) {
            cnt1++;
        } else {
            cnt0++;
        }
        for (int j = 0; j <= n + 1; j++) {
            dp[0][j] = dp[1][j];
          //  cout << dp[0][j] << ' ';
            dp[1][j] = 0;
        }
        //cout << endl;
    }
    int res = dp[0][n];
    res = mul(res, powm(powm(2, n), Mod - 2));
    cout << res << '\n';
    return 0;       
}

Subtask #1
6.0 / 6.0

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

Subtask #2
52.0 / 52.0

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

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 5 ms 1408 KB Output is correct
12 Correct 5 ms 1408 KB Output is correct
13 Correct 5 ms 1408 KB Output is correct
14 Correct 5 ms 1400 KB Output is correct
15 Correct 6 ms 1408 KB Output is correct
16 Correct 5 ms 1408 KB Output is correct
17 Correct 5 ms 1408 KB Output is correct
18 Correct 5 ms 1408 KB Output is correct
19 Correct 5 ms 1408 KB Output is correct
20 Correct 6 ms 1408 KB Output is correct
21 Correct 20 ms 11520 KB Output is correct
22 Correct 19 ms 11520 KB Output is correct
23 Correct 20 ms 11648 KB Output is correct
24 Correct 22 ms 11520 KB Output is correct
25 Correct 18 ms 11648 KB Output is correct
26 Correct 19 ms 11584 KB Output is correct
27 Correct 19 ms 11648 KB Output is correct
28 Correct 18 ms 11648 KB Output is correct
29 Correct 18 ms 11520 KB Output is correct
30 Correct 219 ms 11520 KB Output is correct
31 Correct 119 ms 11520 KB Output is correct
32 Correct 165 ms 11520 KB Output is correct
33 Correct 210 ms 11640 KB Output is correct
34 Correct 117 ms 11648 KB Output is correct
35 Correct 162 ms 11648 KB Output is correct
36 Correct 198 ms 11520 KB Output is correct