Submission #1232712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232712		badge881	Paint By Numbers (IOI16_paint)	C++20	100 / 100	343 ms	331540 KiB

paint

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

using namespace std;
const int MAXN = 2e5 + 5, mod = 1'000'000'007;

int prefixWhite[MAXN], prefixBlack[MAXN];
long long dpCroissant[MAXN][105], dpDecroissant[MAXN][105];

string solve_puzzle(string s, vector<int> c)
{
    string t = s;
    int n = s.size(), m = c.size();
    dpCroissant[0][0] = dpDecroissant[n + 1][m] = 1, s = ' ' + s;
    for (int i = 1; i <= n; i++)
    {
        prefixWhite[i] = prefixWhite[i - 1] + (s[i] == '_');
        prefixBlack[i] = prefixBlack[i - 1] + (s[i] == 'X');
    }
    for (int i = 1; i <= n + 1; i++)
        for (int j = 0; j <= m; j++)
            if (s[i] != 'X')
            {
                dpCroissant[i][j] = dpCroissant[i - 1][j];
                if (j && i > c[j - 1] && prefixWhite[i - 1] == prefixWhite[i - 1 - c[j - 1]])
                    dpCroissant[i][j] = (dpCroissant[i][j] + dpCroissant[i - 1 - c[j - 1]][j - 1]) % mod;
            }
    for (int i = n; i; i--)
        for (int j = 0; j <= m; j++)
            if (s[i] != 'X')
            {
                dpDecroissant[i][j] = dpDecroissant[i + 1][j];
                if (j < m && n - i + 1 > c[j] && prefixWhite[i] == prefixWhite[i + c[j]])
                    dpDecroissant[i][j] = (dpDecroissant[i][j] + dpDecroissant[i + c[j] + 1][j + 1]) % mod;
            }
    for (int i = 1; i <= n; i++)
    {
        long long ans = 0;
        for (int j = 0; j <= m; j++)
            ans = (ans + dpCroissant[i][j] * dpDecroissant[i][j]) % mod;
        if (ans == 0)
            t[i - 1] = 'X';
        else if (ans == dpCroissant[n + 1][m])
            t[i - 1] = '_';
        else
            t[i - 1] = '?';
    }
    return t;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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