oj.uz

Submission #793155

# Submission time Handle Problem Language Result Execution time Memory
793155 2023-07-25T14:35:09 Z Johann Festivals in JOI Kingdom 2 (JOI23_festival2) C++14
87 / 100
 772 ms 306640 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll, ll> pii;
pii operator+(const pii &a, const pii &b) { return {a.first + b.first, a.second + b.second}; }
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

ll N, P;
int dp[6001][3001][8]; // pos, brackets opened and usable by opt, flag with 6 states
// states: 00x no bracket for bad
//         01x bracket for bad but not usable by opt
//         10x undefined...
//         11x bracket for bad and usable by opt
// if x == 0: both have the same score, x == 1: optimal is one better
vi fac, facinv;

ll fast_exp(ll base, ll exp, ll MOD)
{
    ll ans = 1;
    while (exp > 0)
    {
        if (exp & 1)
            ans = (ans * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> P;

    fac.resize(2 * N + 3);
    facinv.resize(sz(fac));
    fac[0] = 1;
    facinv[0] = 1;
    for (ll i = 1; i < sz(fac); ++i)
    {
        fac[i] = (fac[i - 1] * i) % P;
        facinv[i] = fast_exp(fac[i], P - 2, P);
    }

    int dim1 = 2 * N + 1, dim2 = N + 1, dim3 = 8;
    // dp.assign(dim1, vvi(dim2, vi(dim3, 0)));
    // int dpp[2 * N + 1][N + 1][8];
    // for (int pos = 0; pos < sz(dp); ++pos)
    // dp[pos].assign(dim2, vi(dim3, 0));
    dp[0][0][0] = 1;
    for (int pos = 0; pos < 2 * N; ++pos)
    {
        int space = 2 * N - pos;
        for (int bropt = 0; bropt < dim2 && pos + bropt <= 2 * N; ++bropt)
        {
            for (int st = 0; st < dim3; ++st)
            {
                if (dp[pos][bropt][st] == 0)
                    continue;

                bool optBetter = st & 1;
                bool bracketForBad = st & 2;
                bool bracketUsableForOpt = st & 4;

                if (!bracketForBad && bracketUsableForOpt)
                    continue;

                ll dpvalue = dp[pos][bropt][st];
                ll newdpvalue;

                // open bracket
                if (bropt < dim2 - 1)
                {
                    int nst = st;
                    if (!bracketForBad)
                        nst |= 0b110;
                    dp[pos + 1][bropt + 1][nst] = (dpvalue + dp[pos + 1][bropt + 1][nst]) % P;
                }

                // close bracket
                if (bropt == 0 && !bracketForBad)
                    continue;

                if (bracketForBad)
                {
                    if (bracketUsableForOpt)
                    {
                        assert(bropt > 0);

                        // closing both
                        newdpvalue = dpvalue;
                        newdpvalue = (newdpvalue * fac[space - 1]) % P;
                        newdpvalue = (newdpvalue * facinv[space - bropt]) % P;
                        dp[pos + bropt][0][optBetter] = (newdpvalue + dp[pos + bropt][0][optBetter]) % P;

                        // closing opt and all others apart from bad
                        if (!optBetter)
                        {
                            newdpvalue = (dpvalue * (bropt - 1)) % P;
                            newdpvalue = (newdpvalue * fac[space - 1]) % P;
                            newdpvalue = (newdpvalue * facinv[space - bropt + 1]) % P;
                            int nst = 0b011; // bracket for bad by default true
                            dp[pos + bropt - 1][0][nst] = (newdpvalue + dp[pos + bropt - 1][0][nst]) % P;
                        }
                    }
                    else // bracket not usable for opt
                    {
                        // closing only bad
                        assert(optBetter);
                        int nst = 0;
                        dp[pos + 1][bropt][nst] = (dpvalue + dp[pos + 1][bropt][nst]) % P;

                        // closing only opt
                        // well because of the assert this cannot happen...
                    }
                }
                else
                {
                    if (!optBetter)
                    {
                        int nst = 1; // bracket for bad by default false
                        newdpvalue = dpvalue;
                        newdpvalue = (newdpvalue * bropt) % P;
                        newdpvalue = (newdpvalue * fac[space - 1]) % P;
                        newdpvalue = (newdpvalue * facinv[space - bropt]) % P;
                        dp[pos + bropt][0][nst] = (newdpvalue + dp[pos + bropt][0][nst]) % P;
                    }
                }
            }
        }
    }

    ll ans = 1;
    for (ll i = 1; i < 2 * N; i += 2)
        ans = (ans * i) % P;

    ans = (ans - dp[2 * N][0][0] + P) % P;

    cout << ans << "\n";

    return 0;
}

Compilation message

festival2.cpp: In function 'int main()':
festival2.cpp:54:9: warning: unused variable 'dim1' [-Wunused-variable]
   54 |     int dim1 = 2 * N + 1, dim2 = N + 1, dim3 = 8;
      |         ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 456 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 456 KB Output is correct
19 Correct 9 ms 5588 KB Output is correct
20 Correct 9 ms 5588 KB Output is correct
21 Correct 9 ms 5516 KB Output is correct
22 Correct 1 ms 712 KB Output is correct
23 Correct 2 ms 1364 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 456 KB Output is correct
19 Correct 9 ms 5588 KB Output is correct
20 Correct 9 ms 5588 KB Output is correct
21 Correct 9 ms 5516 KB Output is correct
22 Correct 1 ms 712 KB Output is correct
23 Correct 2 ms 1364 KB Output is correct
24 Correct 766 ms 306640 KB Output is correct
25 Correct 761 ms 305068 KB Output is correct
26 Correct 772 ms 305000 KB Output is correct
27 Correct 13 ms 6344 KB Output is correct
28 Correct 136 ms 58180 KB Output is correct
29 Correct 108 ms 48380 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 456 KB Output is correct
19 Correct 9 ms 5588 KB Output is correct
20 Correct 9 ms 5588 KB Output is correct
21 Correct 9 ms 5516 KB Output is correct
22 Correct 1 ms 712 KB Output is correct
23 Correct 2 ms 1364 KB Output is correct
24 Correct 766 ms 306640 KB Output is correct
25 Correct 761 ms 305068 KB Output is correct
26 Correct 772 ms 305000 KB Output is correct
27 Correct 13 ms 6344 KB Output is correct
28 Correct 136 ms 58180 KB Output is correct
29 Correct 108 ms 48380 KB Output is correct
30 Runtime error 22 ms 752 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -