Submission #598935

#	Time	Username	Problem	Language	Result	Execution time	Memory
598935		snasibov05	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2095 ms	8320 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <bits/stdc++.h>

using namespace std;

const int mxn = 2e5 + 5, mxk = 1e2 + 5;
bool pref[mxn][mxk][2];
bool suf[mxn][mxk][2];

string solve_puzzle(string s, vector<int> c) {
    int n = s.size();
    int k = c.size();
    s = ' ' + s;

    pref[0][0][0] = true;
    for (int i = 1; i <= n; ++i){
        for (int j = 0; j <= k; ++j) {
            if (s[i] == '.' || s[i] == '_') pref[i][j][0] = pref[i-1][j][0] || pref[i-1][j][1];
            if (s[i] == 'X' || s[i] == '.') {
                if (j == 0) continue;
                bool flag = true;
                for (int l = i - c[j-1] + 1; l <= i; ++l){
                    if (l <= 0 || s[l] == '_') flag = false;
                }
                if (!flag || !pref[i - c[j-1]][j-1][0]) continue;
                pref[i][j][1] = true;
            }
        }
    }

    suf[n+1][k+1][0] = true;
    for (int i = n; i >= 1; --i){
        for (int j = k+1; j >= 1; --j) {
            if (s[i] == '.' || s[i] == '_') suf[i][j][0] = suf[i+1][j][0] || suf[i+1][j][1];
            if (s[i] == 'X' || s[i] == '.') {
                if (j == k+1) continue;
                bool flag = true;
                for (int l = i; l < i + c[j-1]; ++l){
                    if (l > n || s[l] == '_') flag = false;
                }
                if (!flag || !suf[i + c[j-1]][j+1][0]) continue;
                suf[i][j][1] = true;
            }
        }
    }

    vector<bool> posb(n+1), posw(n+1);
    for (int i = 1; i <= n; ++i){
        if (s[i] == 'X') continue;
        for (int j = 0; j <= k; ++j) {
            posw[i] = posw[i] || ((pref[i-1][j][1] || pref[i-1][j][0]) && (suf[i+1][j+1][1] || suf[i+1][j+1][0]));
        }
    }

    for (int j = 1; j <= k; ++j){
        for (int i = 1; i <= n; ++i) {
            if (!pref[i-1][j-1][0] || !suf[i + c[j-1]][j+1][0]) continue;
            bool flag = true;
            for (int l = i; l < i + c[j-1]; ++l) {
                if (s[l] == '_') flag = false;
            }
            if (!flag) continue;
            for (int l = i; l < i + c[j-1]; ++l){
                posb[l] = true;
            }
        }
    }

    string res;
    for (int i = 1; i <= n; ++i){
        if (posw[i] && posb[i]) res.push_back('?');
        else if (posw[i]) res.push_back('_');
        else res.push_back('X');
    }

    return res;
}

• 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