Submission #1137743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137743		jerzyk	Paint By Numbers (IOI16_paint)	C++20	90 / 100	720 ms	190736 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 = 5007;
int dp[N][N][2];
int sum[N], kon[N];
bool cz1[N], cz0[N];

string solve_puzzle(string s, vector<int> c)
{
    int n = s.size(), m = c.size();
    s = '+' + s;
    for(int i = 1; i <= m; ++i)
    {
        sum[i] = sum[i - 1] + c[i - 1];
        kon[sum[i]] = 1;
        //cerr << i << " " << sum[i] << "\n";
    }
    kon[0] = 1;
    dp[0][0][0] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= sum[m]; ++j)
        {
            //cerr << "\nDP: " << i << " " << j << " ";
            if(kon[j] && s[i] != 'X' && (dp[i - 1][j][0] || dp[i - 1][j][1]))
                dp[i][j][0] = 1;
            //cerr << dp[i][j][0] << " ";
            if(j == 0) continue;
            if(s[i] != '_' && ((!kon[j - 1] && dp[i - 1][j - 1][1]) || (kon[j - 1] && dp[i - 1][j - 1][0])))
                dp[i][j][1] = 1;
            //cerr << dp[i][j][1] << " ";

        }
    //cerr << "\n";
    if(dp[n][sum[m]][0])
        dp[n][sum[m]][0] = 2;
    if(dp[n][sum[m]][1])
        dp[n][sum[m]][1] = 2;
    for(int i = n; i >= 1; --i)
        for(int j = 0; j <= sum[m]; ++j)
        {
            if(dp[i][j][0] < 2) dp[i][j][0] = 0;
            if(dp[i][j][1] < 2) dp[i][j][1] = 0;
            if(dp[i][j][0]) cz0[i] = 1;
            if(dp[i][j][1]) cz1[i] = 1;

            if(dp[i][j][0] && dp[i - 1][j][0])
                dp[i - 1][j][0] = 2;
            if(dp[i][j][0] && dp[i - 1][j][1])
                dp[i - 1][j][1] = 2;
            if(j == 0) continue;
            if(dp[i][j][1] && (!kon[j - 1] && dp[i - 1][j - 1][1]))
                dp[i - 1][j - 1][1] = 2;
            if(dp[i][j][1] && (kon[j - 1] && dp[i - 1][j - 1][0]))
                dp[i - 1][j - 1][0] = 2;
        }
    string ans;
    for(int i = 1; i <= n; ++i)
    {
        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: 10 / 10
• Subtask 7: 0 / 10