Submission #819985

#	Time	Username	Problem	Language	Result	Execution time	Memory
819985		Kerim	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2062 ms	28268 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 i = 1; i <= n; i++)
        if (s[i] == '.')
            for (int j = 1; j <= k; j++){
                for (int h = max(i+c[j]-n,1); h <= min(i, c[j]); h++){
                    
                    if (white[i + c[j] - h] != white[i - h])
                        continue;
                    if (i - h >= 1 and s[i-h] == 'X')
                        continue;
                    if (i + c[j] - h + 1 <= n and s[i + c[j] - h + 1] == 'X')
                        continue;
                    if (i - h == 0){
                        if (j == 1 and suf[i+c[j]-h+2][j+1])
                            answer[i] |= 2;
                        continue;
                    }
                    if (pref[i - h - 1][j-1] and suf[i+c[j]-h+2][j+1])
                        answer[i] |= 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: 0 / 10