Submission #388865

#	Time	Username	Problem	Language	Result	Execution time	Memory
388865		ParsaAlizadeh	Paint By Numbers (IOI16_paint)	C++17	100 / 100	611 ms	31848 KiB

paint

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

string solve_puzzle(string s, vector<int> c) {
    s = "_" + s;

    int const N = s.size();
    int const K = c.size();

    vector<int> ps(N + 1, 0);
    for (int i = 0; i < N; i++)
        ps[i + 1] = s[i] == '_';
    partial_sum(begin(ps), end(ps), begin(ps));

    vector<vector<bool>> dp(N + 1, vector<bool>(K + 1, false));
    dp[0][0] = true;
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= K; j++) {
            dp[i][j] = dp[i][j] || (s[i - 1] != 'X' && dp[i - 1][j]);
            if (j && i > c[j - 1] && s[i - c[j - 1] - 1] != 'X' && ps[i] - ps[i - c[j - 1]] == 0) {
                dp[i][j] = dp[i][j] || dp[i - c[j - 1] - 1][j - 1];
            }
        }
    }

    vector<int> cX(N + 1, 0), c_(N, 0);
    vector<vector<bool>> mark(N + 1, vector<bool>(K + 1, false));
    mark[N][K] = true;
    for (int i = N; i >= 1; i--) {
        for (int j = K; j >= 0; j--) {
            if (!mark[i][j])
                continue;
            if (s[i - 1] != 'X' && dp[i - 1][j]) {
                mark[i - 1][j] = true;
                c_[i - 1]++;
            }
            if (
                j &&
                i > c[j - 1] &&
                s[i - c[j - 1] - 1] != 'X' && 
                ps[i] - ps[i - c[j - 1]] == 0 &&
                dp[i - c[j - 1] - 1][j - 1]
            ) {
                mark[i - c[j - 1] - 1][j - 1] = true;
                cX[i - c[j - 1]]++;
                cX[i]--;
                c_[i - c[j - 1] - 1]++;
            }
        }
    }
    partial_sum(begin(cX), end(cX), begin(cX));

    string ans;
    for (int i = 1; i < N; i++) {
        if (s[i] != '.')
            ans.push_back(s[i]);
        else if (c_[i] && cX[i])
            ans.push_back('?');
        else if (c_[i])
            ans.push_back('_');
        else
            ans.push_back('X');
    }
    return ans;
}

• 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