Submission #1234392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234392		Arturgo	Paint By Numbers (IOI16_paint)	C++20	100 / 100	281 ms	31144 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;

vector<vector<bool>> calcule_dp(string indices, vector<int> blocs) {
    vector<vector<bool>> dp(indices.size(), vector<bool>(blocs.size() + 1, false));

    vector<int> nbBlancsAvant(indices.size() + 1, 0);
    for(int pos = 0;pos < (int)indices.size();pos++) {
        nbBlancsAvant[pos + 1] = nbBlancsAvant[pos] + (int)(indices[pos] == '_');
    }
    
    dp[0][0] = true;
    for(int pos = 0;pos < (int)indices.size() - 1;pos++) {
        for(int blocs_poses = 0;blocs_poses <= blocs.size();blocs_poses++) {
            if(!dp[pos][blocs_poses]) continue;

            if(blocs_poses < blocs.size()
            && pos + blocs[blocs_poses] + 1 < indices.size()
            && indices[pos + blocs[blocs_poses] + 1] != 'X'
            && nbBlancsAvant[pos + blocs[blocs_poses] + 1] == nbBlancsAvant[pos + 1]) {
                dp[pos + blocs[blocs_poses] + 1][blocs_poses + 1] = true;
            }

            if(indices[pos + 1] != 'X') {
                dp[pos + 1][blocs_poses] = true;
            }
        }
    }

    return dp;
}

string solve_puzzle(string indices, vector<int> blocs) {
    indices = "_" + indices + "_";

    auto rindices = indices; reverse(rindices.begin(), rindices.end());
    auto rblocs = blocs; reverse(rblocs.begin(), rblocs.end());
    auto dpAvant = calcule_dp(indices, blocs);
    auto dpApres = calcule_dp(rindices, rblocs);
    reverse(dpApres.begin(), dpApres.end());

    for(int pos = 1;pos < indices.size() - 1;pos++) {
        bool peutBlanc = false;
        for(int blocs_avant = 0;blocs_avant <= blocs.size();blocs_avant++) {
            peutBlanc |= (dpAvant[pos][blocs_avant] && dpApres[pos][blocs.size() - blocs_avant]);
        }
        if(!peutBlanc) indices[pos] = 'X';
    }

    vector<int> nbBlancsAvant(indices.size() + 1, 0);
    for(int pos = 0;pos < (int)indices.size();pos++) {
        nbBlancsAvant[pos + 1] = nbBlancsAvant[pos] + (int)(indices[pos] == '_');
    }

    vector<int> delta(indices.size() + 1, 0);
    for(int pos = 0;pos < indices.size();pos++) {
        for(int blocs_avant = 0;blocs_avant < blocs.size();blocs_avant++) {
            if(pos + blocs[blocs_avant] + 1 < indices.size()
            && dpAvant[pos][blocs_avant] 
            && dpApres[pos + blocs[blocs_avant] + 1][blocs.size() - 1 - blocs_avant]
            && nbBlancsAvant[pos + blocs[blocs_avant] + 1] == nbBlancsAvant[pos + 1]) {
                delta[pos + 1] += 1;
                delta[pos + blocs[blocs_avant] + 1] -= 1;
            }
        }
    }

    int somme = 0;
    for(int pos = 0;pos < indices.size();pos++) {
        somme += delta[pos];
        if(somme == 0) {
            indices[pos] = '_';
        }
    }

    replace(indices.begin(), indices.end(), '.', '?');
    return string(indices.begin() + 1, indices.end() - 1);
}

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