Submission #64123

#	Time	Username	Problem	Language	Result	Execution time	Memory
64123		KHUSRAV	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1128 ms	31872 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std ;
string solve_puzzle(string s, vector<int> c) {
    int L = s.size() , N = c.size();
    vector<vector<bool> > prefix(L + 1 , vector<bool> (N + 1 , 0)) , suffix(L + 1 , vector<bool> (N + 1 , 0));
    vector<bool> white(L + 1 , 0) , black(L + 1 , 0) , B(L + 1 , 0) , W(L + 1 , 0);


    for(int i = 0 ; i < L ; i++){
        if(s[i] == 'X')
            B[i] = 1 ;
        if(s[i] == '_')
            W[i] = 1 ;
    }
    prefix[0][0] = 1 ;

    for(int i = 1 ; i <= L ; i++ ){
        if(B[i - 1] == 0)
            prefix[i][0] = prefix[i - 1][0];
        else prefix[i][0] = 0;
    }
    vector<int> Ws(L + 1 , 0);
    for(int j = 1 ; j <= L ; j ++)
        Ws[j] = Ws[j - 1] + W[j - 1];


    for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j <= L ; j ++){
            if(B[j - 1] == 0 && prefix[j - 1][i] == 1)
                prefix[j][i] = 1 ;

            if(W[j - 1] == 0){
                int kol = c[i - 1];
                if (j < kol)
                    continue;
                if (Ws[j] - Ws[j - kol] > 0)
                    continue;
                if (j > kol && B[j - kol - 1])
                    continue;
                if (prefix[max(0 , j - kol - 1)][i - 1])
                    prefix[j][i] = 1;
            }
        }

    }

    reverse(B.begin() , B.end() - 1);
    reverse(W.begin() , W.end() - 1);
    reverse(c.begin() , c.end());

    suffix[0][0] = 1 ;

    for(int i = 1 ; i <= L ; i++ ){
        if(B[i - 1] == 0)
            suffix[i][0] = suffix[i - 1][0];
        else suffix[i][0] = 0 ;
    }
    for(int i = 0 ; i <= L ; i++)
        Ws[i] = 0 ;

    for(int j = 1 ; j <= L ; j ++)
        Ws[j] = Ws[j - 1] + W[j - 1];

    for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j <= L ; j ++){
            if(B[j - 1] == 0 && suffix[j - 1][i])
                suffix[j][i] = 1 ;

            if(W[j - 1] == 0){
                int kol = c[i - 1];
                if (j < kol)
                    continue;
                if (Ws[j] - Ws[j - kol] > 0)
                    continue;
                if (j > kol && B[j - kol - 1])
                    continue;
                if (suffix[max(0 , j - kol - 1)][ i - 1])
                    suffix[j][i] = 1;
            }
        }

    }

    reverse(B.begin() , B.end() - 1);
    reverse(W.begin() , W.end() - 1);
    reverse(c.begin() , c.end());
    for(int i = 0 ; i < L ; i++){
        for(int j = 0 ; j <= N ; j++){
            if(B[i] == 0 && prefix[i][j] && suffix[L - i - 1][N - j])
                white[i] = 1 ;
        }



    }


    vector<int> l(L + 1 , 0);
    for(int i = 0 ; i <= L; i++)
        Ws[i] = 0 ;
    for(int j = 1 ; j <= L ; j ++)
        Ws[j] = Ws[j - 1] + W[j - 1];

    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j + c[i] <= L ; j ++){
            if(j > 0 && B[j - 1])
                continue;
            if(j + c[i] < L && B[j + c[i]])
                continue;
            if(Ws[j + c[i]] - Ws[j] > 0)
                continue;

            if(prefix[max(0 , j - 1)][i] && suffix[max(0 , L - (j + c[i]) - 1)][N - i  - 1]){
                l[j] += 1;
                l[j + c[i]] -= 1;
            }
        }
    }

    int ss = 0 ;
    for(int i = 0 ; i < L ; i ++){
        ss += l[i];
        if(ss > 0)
            black[i] = 1 ;
    }
    string ans = "";
    for(int i = 0 ; i < L ; i++){
        if(black[i] && white[i])
            ans += '?';
        if(black[i] && white[i] == 0)
            ans += 'X';
        if(black[i]  == 0 && white[i] == 1)
            ans += '_';
    }
    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