Submission #64120

#	Time	Username	Problem	Language	Result	Execution time	Memory
64120		KHUSRAV	Paint By Numbers (IOI16_paint)	C++14	0 / 100	3 ms	248 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<int> > prefix(L + 1 , vector<int> (N + 1 , 0)) , suffix(L + 1 , vector<int> (N + 1 , 0));
    vector<int> white(L + 1 , 0) , black(L + 1 , 0) , B(L + 1 , 0) , W(L + 1 , 0);
    cout << B.size()<<'\n';
    cout << c.size()<<'\n';
    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] == 1)
                    continue;
                if (prefix[max(0 , j - kol - 1)][i - 1] == 1)
                    prefix[j][i] = 1;
            }
        }
        for(int j = 1 ; j <= L ; j ++)
            cout <<prefix[j][i];
        cout <<'\n';
    }

    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] == 1)
                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] == 1)
                    continue;
                if (suffix[max(0 , j - kol - 1)][ i - 1] == 1)
                    suffix[j][i] = 1;
            }
        }
        for(int j = 1 ; j <= L ; j++)
            cout << suffix[j][i];

        cout <<'\n';
    }

    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] == 1 && suffix[L - i - 1][N - j] == 1)
                white[i] = 1 ;
        }
        cout << white[i];


    }

    cout <<'\n';
    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] == 1)
                continue;
            if(j + c[i] < L && B[j + c[i]] == 1)
                continue;
            if(Ws[j + c[i]] - Ws[j] > 0)
                continue;

            if(prefix[max(0 , j - 1)][i] == 1 && suffix[max(0 , L - (j + c[i]) - 1)][N - i  - 1] == 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] == 1 && white[i] == 1)
            ans += '?';
        if(black[i] == 1 && white[i] == 0)
            ans += 'X';
        if(black[i]  == 0 && white[i] == 1)
            ans += '_';
    }
    return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10