Submission #702216

# Submission time Handle Problem Language Result Execution time Memory
702216 2023-02-23T10:25:52 Z LittleCube Bowling (BOI15_bow) C++14
16 / 100
1000 ms 125544 KB
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

ll dp[11][66][66][331];
short cost[66][66][66], cost223[66][66][331], cost23[66][331], cost3[331], can[11][331];
const int s2 = 66, s3 = 241;
string mp2[s2], mp3[s3];

int _cost(string s, string t)
{
    int a = -1, b = -1;
    for (auto c : t)
    {
        if (c == 'x')
            (a == -1 ? a : b) = 10;
        else if (c == '/')
            b = 10 - a;
        else if (isdigit(c))
            (a == -1 ? a : b) = c - '0';
        if (b >= 0)
            break;
    }
    a = max(0, a), b = max(0, b);

    if (s[0] == 'x')
        return 10 + a + b;
    else if (s[1] == '/')
        return 10 + a;
    else
        return s[0] + s[1] - 2 * '0';
}

bool match(string s, string t)
{
    for (int i = 0; i < s.size(); i++)
        if (s[i] != t[i] && s[i] != '?')
            return 0;
    return 1;
}

void solve()
{
    string s;
    int n, ans[13] = {};
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
        cin >> ans[i + 2];
    dp[0][0][0][0] = 1;
    for (int i = 1; i <= n - 1; i++)
        for (int j = 0; j < s2; j++)
            for (int k = 0; k < s2; k++)
                for (int sc = 0; sc <= 330; sc++)
                    dp[i][j][k][sc] = 0;
    for (int i = 0; i <= n - 2; i++)
    {
        string t = s.substr(2 * i, 2);
        for (int l = 0; l < s2; l++)
            can[i][l] = match(t, mp2[l]);
    }
    vector<tuple<int, int, int>> state, nxt;
    nxt.emplace_back(make_tuple(0, 0, 0));
    for (int i = 0; i <= n - 2; i++)
    {
        state.swap(nxt);
        nxt.clear();
        for (auto [j, k, sc] : state)
            for (int l = 0; l < s2; l++)
                if (can[i][l] && (sc + cost[j][k][l] == ans[i + 1] || ans[i + 1] == -1))
                {
                    if (dp[i + 1][k][l][sc + cost[j][k][l]] == 0)
                        nxt.emplace_back(make_tuple(k, l, sc + cost[j][k][l]));
                    dp[i + 1][k][l][sc + cost[j][k][l]] += dp[i][j][k][sc];
                }
    }

    ll res = 0;
    for (int l = 0; l < s3; l++)
        can[n - 1][l] = match(s.substr(2 * n - 2, 3), mp3[l]);

    state.swap(nxt);
    for (auto [j, k, sc] : state)
        for (int l = 0; l < s3; l++)
            if (can[n - 1][l])
            {
                int an2 = cost223[j][k][l], an1 = an2 + cost23[k][l], an = an1 + cost3[l];
                if (dp[n - 1][j][k][sc] != 0 &&
                    (sc + an2 == ans[n] || ans[n] == -1) &&
                    (sc + an1 == ans[n + 1] || ans[n + 1] == -1) &&
                    (sc + an == ans[n + 2] || ans[n + 2] == -1))
                    res += dp[n - 1][j][k][sc];
            }
    cout << res << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int idx = 0;
    for (int i = 0; i <= 10; i++)
        for (int j = 0; j <= 10 - i; j++)
        {
            string s = (i == 10 ? "x-" : (i + j == 10 ? string(1, '0' + i) + "/" : string(1, '0' + i) + string(1, '0' + j)));
            mp2[idx] = s;
            idx++;
        }
    idx = 0;
    for (int i = 0; i <= 10; i++)
        for (int j = 0; j <= (i == 10 ? 10 : 10 - i); j++)
            for (int k = 0; k <= (i == 10 ? (j == 10 ? 10 : 10 - j) : (i + j == 10 ? 10 : 0)); k++)
            {
                string s = (i == 10 ? "x" : string(1, '0' + i)) +
                           (j == 10 ? "x" : string(1, '0' + j)) +
                           (k == 10 ? "x" : string(1, '0' + k));
                if (i < 10 && i + j == 10)
                    s[1] = '/';
                if (i == 10 && j < 10 && j + k == 10)
                    s[2] = '/';
                if (i + j < 10)
                    s[2] = '-';
                mp3[idx] = s;
                idx++;
            }
    for (int j = 0; j < s2; j++)
        for (int k = 0; k < s2; k++)
            for (int l = 0; l < s2; l++)
                cost[j][k][l] = _cost(mp2[j], mp2[k] + mp2[l]);
    for (int j = 0; j < s2; j++)
        for (int k = 0; k < s2; k++)
            for (int l = 0; l < s3; l++)
                cost223[j][k][l] = _cost(mp2[j], mp2[k] + mp3[l]);
    for (int k = 0; k < s2; k++)
        for (int l = 0; l < s3; l++)
            cost23[k][l] = _cost(mp2[k], mp3[l]);
    for (int l = 0; l < s3; l++)
    {
        short &an = cost3[l];

        if (mp3[l][1] == '/')
        {
            an += 10;
            if (mp3[l][2] != '-')
                an += (mp3[l][2] == 'x' ? 10 : mp3[l][2] - '0');
        }
        else
        {
            an += (mp3[l][0] == 'x' ? 10 : mp3[l][0] - '0');
            if (mp3[l][2] == '/')
                an += 10;
            else
            {
                an += (mp3[l][1] == 'x' ? 10 : mp3[l][1] - '0');
                if (mp3[l][2] != '-')
                    an += (mp3[l][2] == 'x' ? 10 : mp3[l][2] - '0');
            }
        }
    }

    cerr << "start\n";
    int q;
    cin >> q;
    while (q--)
        solve();
}

Compilation message

bow.cpp: In function 'bool match(std::string, std::string)':
bow.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < s.size(); i++)
      |                     ~~^~~~~~~~~~
bow.cpp: In function 'void solve()':
bow.cpp:72:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |         for (auto [j, k, sc] : state)
      |                   ^
bow.cpp:87:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |     for (auto [j, k, sc] : state)
      |               ^
# Verdict Execution time Memory Grader output
1 Correct 163 ms 106344 KB Output is correct
2 Correct 181 ms 94196 KB Output is correct
3 Correct 195 ms 94036 KB Output is correct
4 Correct 207 ms 105324 KB Output is correct
5 Correct 207 ms 105500 KB Output is correct
6 Correct 267 ms 105272 KB Output is correct
7 Correct 252 ms 105412 KB Output is correct
8 Correct 227 ms 105464 KB Output is correct
9 Correct 218 ms 105468 KB Output is correct
10 Correct 248 ms 105480 KB Output is correct
11 Correct 333 ms 105424 KB Output is correct
12 Correct 75 ms 15052 KB Output is correct
13 Correct 51 ms 14944 KB Output is correct
14 Correct 74 ms 15056 KB Output is correct
15 Correct 52 ms 15056 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 121836 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 125544 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 125528 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 163 ms 106344 KB Output is correct
2 Correct 181 ms 94196 KB Output is correct
3 Correct 195 ms 94036 KB Output is correct
4 Correct 207 ms 105324 KB Output is correct
5 Correct 207 ms 105500 KB Output is correct
6 Correct 267 ms 105272 KB Output is correct
7 Correct 252 ms 105412 KB Output is correct
8 Correct 227 ms 105464 KB Output is correct
9 Correct 218 ms 105468 KB Output is correct
10 Correct 248 ms 105480 KB Output is correct
11 Correct 333 ms 105424 KB Output is correct
12 Correct 75 ms 15052 KB Output is correct
13 Correct 51 ms 14944 KB Output is correct
14 Correct 74 ms 15056 KB Output is correct
15 Correct 52 ms 15056 KB Output is correct
16 Execution timed out 1020 ms 121836 KB Time limit exceeded
17 Halted 0 ms 0 KB -