Submission #1151399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151399		jerzyk	Paint By Numbers (IOI16_paint)	C++20	80 / 100	2 ms	4420 KiB

paint

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 200'07;
const int K = 103;
int dp[N][K][2];
int sum[N];
int cz1[N], cz0[N];

string solve_puzzle(string s, vector<int> c)
{
    int n = s.size(), k = c.size();
    s = '+' + s;
    for(int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + (int)(s[i] == '_');
    dp[0][0][0] = 1;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; s[i] != 'X' && j <= k; ++j)
            dp[i][j][0] |= (dp[i - 1][j][0] | dp[i - 1][j][1]);
        for(int j = 1; j <= k && s[i] != '_'; ++j)
            if(sum[i] - sum[i - c[j - 1]] == 0)
                dp[i][j][1] |= dp[i - c[j - 1]][j - 1][0];
    }
    if(dp[n][k][0] == 1) dp[n][k][0] = 2;
    if(dp[n][k][1] == 1) dp[n][k][1] = 2;
    for(int i = n; i >= 1; --i)
    {
        for(int j = 0; j <= k; ++j)
        {
            if(dp[i][j][0] != 2) continue;
            cz0[i] = 1;
            if(dp[i - 1][j][0] == 1)
                dp[i - 1][j][0] = 2;
            if(dp[i - 1][j][1] == 1)
                dp[i - 1][j][1] = 2;
        }
        for(int j = 1; j <= k; ++j)
        {
            if(dp[i][j][1] != 2) continue;
            cz1[i - c[j - 1] + 1] += 1; cz1[i + 1] -= 1;
            if(dp[i - c[j - 1]][j - 1][0] == 1)
                dp[i - c[j - 1]][j - 1][0] = 2;
        }
    }
    string ans;
    for(int i = 1; i <= n; ++i)
    {
        cz1[i] += cz1[i - 1];
        if(cz1[i] && cz0[i])
            ans.pb('?');
        else
        {
            if(cz1[i])
                ans.pb('X');
            else
                ans.pb('_');
        }
    }
    return ans;
}

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: 0 / 10
• Subtask 7: 0 / 10