Submission #212562

#	Time	Username	Problem	Language	Result	Execution time	Memory
212562		egorlifar	Ruins 3 (JOI20_ruins3)	C++17	100 / 100	219 ms	11648 KiB

ruins3

/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#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 / 6
• Subtask 2: 52 / 52
• Subtask 3: 42 / 42