Submission #819990

#	Time	Username	Problem	Language	Result	Execution time	Memory
819990		Kerim	Paint By Numbers (IOI16_paint)	C++17	100 / 100	475 ms	32028 KiB

paint

#include "paint.h"
#include "bits/stdc++.h"

using namespace std;

string solve_puzzle(string s, vector<int> c) {
    int n = s.size(), k = c.size();
    s = "$" + s + "$";
    vector<int> white(n+2, 0), black(n+2, 0);
    for (int i = 1; i <= n+1; i++){
        white[i] = white[i-1] + (s[i] == '_');
        black[i] = black[i-1] + (s[i] == 'X');
    }
    reverse(c.begin(), c.end());
    c.push_back(-1);
    reverse(c.begin(), c.end());
    vector<vector<bool> > pref(n+3, vector<bool>(k+2, 0));
    vector<vector<bool> > suf(n+3, vector<bool>(k+2, 0));
    
    for (int i = 0; i <= n+2; i++){
        pref[i][0] = black[i] == 0;
        suf[i][k+1] = black[n] == black[i - 1];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++){
            if (s[i] != 'X')
                pref[i][j] = pref[i-1][j];
            if (i >= c[j] and white[i] == white[i-c[j]]){
                if (i == c[j]){
                    if (j == 1)
                        pref[i][j] = true;
                }
                else if (s[i-c[j]] != 'X')
                    pref[i][j] = pref[i][j] | pref[i-c[j]-1][j-1];
            }
        }
    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= k; j++){
            if (s[i] != 'X')
                suf[i][j] = suf[i+1][j];
            if (i + c[j] <= n+1 and white[i+c[j]-1] == white[i-1] and s[i+c[j]] != 'X')
                suf[i][j] = suf[i][j] | suf[i+c[j]+1][j+1];
        }
    //put white
    vector<int> answer(n+1, 0);
    for (int i = 1; i <= n; i++)
        if (s[i] == '.'){
            for (int j = 1; j <= k+1; j++)
                if (pref[i-1][j-1] and suf[i+1][j]){
                    answer[i] |= 1;
                    break;
                }
        }
    //put black
    for (int j = 1; j <= k; j++)
        for (int i = 1; i + c[j] <= n+1; i++){
            int l = i, r = i + c[j] - 1;
            if (white[r] == white[l-1] and s[l-1] != 'X' and s[r+1] != 'X'){
                if (l==1){
                    if (j == 1 and suf[r+2][j+1]){
                        for (int h = l; h <= r; h++)
                            answer[h] |= 2;
                    }
                }
                else if(pref[l-2][j-1] and suf[r+2][j+1]){
                    for (int h = l; h <= r; h++)
                        answer[h] |= 2;
                }
            }
        }
    string result;
    for (int i = 1; i <= n; i++){
        if (s[i] == '.'){
            if (answer[i] == 1)
                result += '_';
            else if(answer[i] == 2)
                result += 'X';
            else    
                result += '?';
        }
        else
            result += s[i];
    }
    return result;
}

• 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