Submission #1226365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226365		vladilius	Paint By Numbers (IOI16_paint)	C++20	100 / 100	363 ms	82276 KiB

paint

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

string solve_puzzle(string s, vector<int> c){
    int n = (int) s.size(), k = (int) c.size();
    
    s = '#' + s; c.insert(c.begin(), 0);
    
    vector<int> p1(n + 1);
    for (int i = 1; i <= n; i++){
        p1[i] = p1[i - 1];
        if (s[i] == '_'){
            p1[i]++;
        }
    }
    
    bool dp1[n + 1][k + 1][2];
    for (int i = 0; i <= n; i++){
        for (int j = 0; j <= k; j++){
            dp1[i][j][0] = dp1[i][j][1] = 0;
        }
    }

    dp1[0][0][0] = dp1[0][0][1] = 1;
    
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= k; j++){
            if (s[i] == '.'){
                dp1[i][j][0] = max(dp1[i - 1][j][0], dp1[i - 1][j][1]);
                if (j && i >= c[j] && p1[i] == p1[i - c[j]]){
                    dp1[i][j][1] = dp1[i - c[j]][j - 1][0];
                }
            }
            else if (s[i] == 'X'){
                if (j && i >= c[j] && p1[i] == p1[i - c[j]]){
                    dp1[i][j][1] = dp1[i - c[j]][j - 1][0];
                }
            }
            else {
                dp1[i][j][0] = max(dp1[i - 1][j][0], dp1[i - 1][j][1]);
            }
        }
    }
    
    bool dp2[n + 2][k + 2][2];
    for (int i = 0; i <= n + 1; i++){
        for (int j = 0; j <= k + 1; j++){
            dp2[i][j][0] = dp2[i][j][1] = 0;
        }
    }
    
    dp2[n + 1][k + 1][0] = dp2[n + 1][k + 1][1] = 1;
    
    for (int i = n; i > 0; i--){
        for (int j = 1; j <= k + 1; j++){
            if (s[i] == '.'){
                dp2[i][j][0] = max(dp2[i + 1][j][0], dp2[i + 1][j][1]);
                if (j != (k + 1) && (i + c[j] - 1) <= n && p1[i + c[j] - 1] == p1[i - 1]){
                    dp2[i][j][1] = dp2[i + c[j]][j + 1][0];
                }
            }
            else if (s[i] == 'X'){
                if (j != (k + 1) && (i + c[j] - 1) <= n && p1[i + c[j] - 1] == p1[i - 1]){
                    dp2[i][j][1] = dp2[i + c[j]][j + 1][0];
                }
            }
            else {
                dp2[i][j][0] = max(dp2[i + 1][j][0], dp2[i + 1][j][1]);
            }
        }
    }
    
    vector<int> p(n + 2);
    for (int j = 1; j <= k; j++){
        for (int l = 1; l + c[j] - 1 <= n; l++){
            if (dp1[l - 1][j - 1][0] && dp2[l + c[j]][j + 1][0] && p1[l + c[j] - 1] == p1[l - 1]){
                p[l]++; p[l + c[j]]--;
            }
        }
    }
    
    int S = 0;
    string out;
    for (int i = 1; i <= n; i++){
        S += p[i];
        if (s[i] == 'X'){
            out += 'X';
            continue;
        }
        if (s[i] == '_'){
            out += '_';
            continue;
        }
        
        bool I1 = 0;
        for (int j = 0; j <= k; j++){
            if (dp1[i][j][0] && dp2[i][j + 1][0]){
                I1 = 1;
                break;
            }
        }
        
        bool I2 = (S > 0);
        
        if (I1 && I2){
            out += '?';
        }
        else if (I1){
            out += '_';
        }
        else {
            out += 'X';
        }
    }
    return out;
}

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