Submission #1071537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071537		TheQuantiX	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	448 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"

using namespace std;
using ll = long long;

constexpr ll MOD = 1000000007;

ll n, m, q, k, x, y, a, b, c;

string solve_puzzle(string s, vector<int> c) {
    n = s.size();
    m = c.size();
    string ans;
    vector< vector<ll> > dp1(m + 1, vector<ll> (n + 1));
    vector< vector<ll> > dp2(m + 1, vector<ll> (n + 1));
    for (int j = 0; j <= m; j++) {
        for (int i = 0; i <= n; i++) {
            if (j == 0) {
                dp1[j][i] = 1;
                continue;
            }
            if (i == 0) {
                dp1[j][i] = 0;
                continue;
            }
            if (j == 1 && i >= c[j - 1]) {
                dp1[j][i] = 1;
            }
            if (j > 1 && i >= c[j - 1] + 1) {
                dp1[j][i] += dp1[j - 1][i - c[j - 1] - 1];
                dp1[j][i] %= MOD;
            }
            dp1[j][i] += dp1[j][i - 1];
            dp1[j][i] %= MOD;
            // cout << j << ' ' << i << ' ' << dp1[j][i] << '\n';
        }
    }
    reverse(c.begin(), c.end());
    for (int j = 0; j <= m; j++) {
        for (int i = 0; i <= n; i++) {
            if (j == 0) {
                dp2[j][i] = 1;
                continue;
            }
            if (i == 0) {
                dp2[j][i] = 0;
                continue;
            }
            if (j == 1 && i >= c[j - 1]) {
                dp2[j][i] = 1;
            }
            if (j > 1 && i >= c[j - 1] + 1) {
                dp2[j][i] += dp2[j - 1][i - c[j - 1] - 1];
                dp2[j][i] %= MOD;
            }
            dp2[j][i] += dp2[j][i - 1];
            dp2[j][i] %= MOD;
        }
    }
    reverse(c.begin(), c.end());
    vector<ll> cnt(n + 1);
    for (int j = 0; j < m; j++) {
        for (int i = c[j] + (j != 0 ? 1 : 0); (n + 1 - i) - 1 - (j != m - 1 ? 1 : 0) >= 0; i++) {
            // cout << j << ' ' << i << endl;
            ll num = dp1[j][i - c[j] - (j != 0 ? 1 : 0)];
            // cout << num << endl;
            // cout << m - 1 - j << ' ' << (n + 1 - i) - 1 - (j != m - 1 ? 1 : 0) << endl;
            num *= dp2[m - 1 - j][(n + 1 - i) - 1 - (j != m - 1 ? 1 : 0)];
            num %= MOD;
            // cout << num << endl;
            cnt[i - c[j]] += num;
            cnt[i - c[j]] %= MOD;
            cnt[i] += MOD - num;
            cnt[i] %= MOD;
            // cout << '\n';
        }
    }
    // cout << "DEBUG" << endl;
    for (int i = 0; i < n; i++) {
        cnt[i] %= MOD;
        // cout << i << ' ' << cnt[i] << endl;
        cnt[i + 1] += cnt[i];
        // cout << i << endl;
        if (cnt[i] == 0) {
            ans += '_';
        }
        else if (cnt[i] == dp1[m][n]) {
            ans += 'X';
        }
        else {
            ans += '?';
        }
    }
    return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10