Submission #1066429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066429		andrei_iorgulescu	Paint By Numbers (IOI16_paint)	C++14	100 / 100	538 ms	253364 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#warning That's not FB, that's my FB

using namespace std;

using integer = int;

int modulo = (int)1e9 + 12345;

int n, k;
int a[200005], v[105];
int spb[200005], spw[200005];
int dp[200005][105], ways[200005][105], spdp[200005][105];
int prev_b[200005];
int p[200005];
int f[200005], spf[200005];

string solve_puzzle(string s, vector<integer> c)
{
    n = s.size();
    k = c.size();
    for (int i = 1; i <= k; i++)
        v[i] = c[i - 1];
    for (int i = 1; i <= n; i++)
    {
        if (s[i - 1] == 'X')
            a[i] = 0;
        else if (s[i - 1] == '_')
            a[i] = 1;
        else
            a[i] = 2;
    }
    prev_b[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 0)
            prev_b[i] = i;
        else
            prev_b[i] = prev_b[i - 1];
    }
    for (int i = 1; i <= n; i++)
    {
        spb[i] = spb[i - 1];
        spw[i] = spw[i - 1];
        if (a[i] == 0)
            spb[i]++;
        else if (a[i] == 1)
            spw[i]++;
    }
    ways[n + 2][k + 1] = 1;
    ways[n + 1][k + 1] = 1;
    for (int i = n; i >= 1; i--)
    {
        if (a[i] != 0)
            ways[i][k + 1] = ways[i + 1][k + 1];
        for (int j = 1; j <= k; j++)
        {
            if (a[i] == 1)
                ways[i][j] = ways[i + 1][j];
            else if (a[i] == 0)
            {
                if (i + v[j] - 1 <= n and spw[i + v[j] - 1] == spw[i - 1])
                {
                    if (i + v[j] == n + 1 or a[i + v[j]] != 0)
                        ways[i][j] = ways[i + v[j] + 1][j + 1];
                }
            }
            else
            {
                if (i + v[j] - 1 <= n and spw[i + v[j] - 1] == spw[i - 1])
                {
                    //cout << i << ' ' << j << endl;
                    if (i + v[j] == n + 1 or a[i + v[j]] != 0)
                        ways[i][j] = ways[i + v[j] + 1][j + 1];
                }
                if (a[i] != 0)
                    ways[i][j] += ways[i + 1][j];
                if (ways[i][j] >= modulo)
                    ways[i][j] -= modulo;
            }
            //cout << i << ' ' << j << ' ' << ways[i][j] << endl;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            if (i - v[j] + 1 >= 1 and spw[i] == spw[i - v[j]] and (i == n or a[i + 1] != 0))
            {
                if (j == 1 and spb[i - v[j]] == 0)
                    dp[i][j] = 1;
                else if (j != 1)
                {
                    int x = prev_b[i - v[j]];
                    if (x == 0)
                        dp[i][j] = spdp[max(0,i - v[j] - 1)][j - 1];
                    else
                        dp[i][j] = (spdp[i - v[j] - 1][j - 1] + modulo - spdp[x - 1][j - 1]) % modulo;
                }
            }
            spdp[i][j] = (spdp[i - 1][j] + dp[i][j]) % modulo;
        }
    }
    int nrw = 0;
    for (int j = 1; j <= k; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            f[i] = (__int128)dp[i][j] * ways[i + 2][j + 1] % modulo;
            spf[i] = (spf[i - 1] + f[i]) % modulo;
        }
        if (j == 1)
            nrw = spf[n];
        for (int i = 1; i <= n; i++)
        {
            int inc = (spf[min(n,i + v[j] - 1)] - spf[i - 1] + modulo) % modulo;
            p[i] = (p[i] + inc) % modulo;
        }
    }
    string ans;
    for (int i = 1; i <= n; i++)
    {
        if (p[i] == 0)
            ans.push_back('_');
        else if (p[i] == nrw)
            ans.push_back('X');
        else
            ans.push_back('?');
    }
    return ans;
}

Compilation message (stderr)

paint.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~

• 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