Submission #200243

#	Time	Username	Problem	Language	Result	Execution time	Memory
200243		mat_v	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1888 ms	161200 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;


int n;
int k;
int blokovi[105];
bool bio[200005][105];
bool dp[200005][105];
int niz[200005];
int pref[200005];
bool check(int poz, int blocc){
    int duz = blokovi[blocc];
    int dokle = poz - duz + 1;
    if(dokle <= 0)return 0;
    int sta = pref[poz] - pref[dokle - 1];
    if(sta > 0)return 0;
    if(niz[dokle - 1] == 1)return 0;
    return 1;
}
bool resi(int poz, int blocc){
    if(poz < -1)return 0;
    if(poz == 0 || poz == -1){
        if(blocc == 0)return 1;
        return 0;
    }
    if(bio[poz][blocc])return dp[poz][blocc];
    bio[poz][blocc] = 1;
    if(niz[poz] == -1){
        ///BELI
        bool pom = resi(poz - 1, blocc);
        dp[poz][blocc] = pom;
        if(blocc == 0)return dp[poz][blocc];
        ///CRNI
        int duz = blokovi[blocc];
        /// dal [poz - duz + 1, poz] svi crni i [poz - duz] beo
        if(check(poz, blocc)){
            pom = resi(poz - duz - 1, blocc - 1);
            dp[poz][blocc] |= pom;
        }
    }
    else{
        if(niz[poz] == 1){
            if(blocc == 0){
                return dp[poz][blocc] = 0;
            }
            int duz = blokovi[blocc];
            if(check(poz, blocc)){
                bool pom = resi(poz - duz - 1, blocc - 1);
                dp[poz][blocc] |= pom;
            }
        }
        else if(niz[poz] == 0){
            dp[poz][blocc] |= resi(poz - 1, blocc);
        }
    }
    return dp[poz][blocc];
}

bool biogore[200005][105];
int dpgore[200005][105];
bool resigore(int poz, int blocc){
    if(poz > n+2)return 0;
    if(poz == n+1 || poz == n+2){
        if(blocc == k+1)return 1;
        return 0;
    }
    if(biogore[poz][blocc])return dpgore[poz][blocc];
    biogore[poz][blocc] = 1;
    bool resenje = 0;
    if(niz[poz] == -1){
        /// BELi
        bool pom = resigore(poz + 1, blocc);
        resenje |= pom;
        /// CRNI
        if(blocc == k+1)return dpgore[poz][blocc] = resenje;
        int duz = blokovi[blocc];
        int kolko = pref[poz + duz - 1] - pref[poz - 1];
        if(kolko == 0){
            if(niz[poz + duz] != 1){
                resenje |= resigore(poz + duz + 1, blocc + 1);
            }
        }
    }
    else{
        if(niz[poz] == 0){
            resenje |= resigore(poz + 1, blocc);
        }
        else if(niz[poz] == 1){
            if(blocc == k+1)return dpgore[poz][blocc] = 0;
            int duz = blokovi[blocc];
            int kolko = pref[poz + duz - 1] - pref[poz - 1];
            if(kolko == 0){
                if(niz[poz + duz] != 1){
                    resenje |= resigore(poz + duz + 1, blocc + 1);
                }
            }
        }
    }
    return dpgore[poz][blocc] = resenje;
}
int moze[200005][2];
std::string solve_puzzle(std::string s, std::vector<int> c) {
    n = s.length();
    k = c.size();
    for(int i=0; i<k; i++)blokovi[i + 1] = c[i];
    for(int i=0; i<n; i++){
        if(s[i] == '.')niz[i + 1] = -1;
        else if(s[i] == 'X')niz[i + 1] = 1;
        else niz[i + 1] = 0;
    }
    for(int i=1; i<=n; i++){
        if(niz[i] == 0)pref[i]++;
        pref[i] += pref[i - 1];
    }
    //cout << resigore(3, 1) << endl;
    //exit(0);
    for(int i=1; i<=n; i++){
        //cout << i << endl;
        /// BELI
        if(niz[i] == 0){
            moze[i][1]++;
        }
        else if(niz[i] == -1){
            bool zemara = 0;
            for(int j=0; j<=k; j++){
                if(resi(i - 1, j) && resigore(i + 1, j + 1))zemara = 1;
            }
            if(zemara){
                moze[i][1]++;
            }
        }
        /// CRNI
        if(niz[i] == 1 || niz[i] == -1){
            for(int j=1; j<=k; j++){
                //bool uslov = 0;
                int zdu = blokovi[j];
                //if(j == k)uslov = 1;
                //if(niz[i + 1] != 1 && resigore(i + 2, j + 1))uslov = 1;
                if(check(i, j)  && niz[i+1] != 1 && resigore(i + 2, j + 1) && resi(i - zdu - 1, j - 1)){
                    int duz = blokovi[j];
                    int posl = i - duz + 1;
                    moze[posl][0]++;
                    moze[i + 1][0]--;
                    //if(2 >= posl && 2 <= i)cout << i << " " << j << endl;
                }
            }
        }
    }
    for(int i=1; i<=n; i++)moze[i][0] += moze[i - 1][0];
    string sol = "";
    for(int i=1; i<=n; i++){
        if(moze[i][0] > 0){
            if(moze[i][1] > 0)sol += '?';
            else sol += 'X';
        }
        else{
            sol += '_';
        }
    }
    return sol;
}


/*
int nn,kk;
string xx;
int main(){
    cin >> xx;
    cin >> kk;
    vector<int>aa;
    for(int i=0; i<kk; i++){
        int bb;
        cin >> bb;
        aa.push_back(bb);
    }
    cout << solve_puzzle(xx, aa);
}
/*


*/

Compilation message (stderr)

paint.cpp:182:1: warning: "/*" within comment [-Wcomment]
 /*
  
paint.cpp: In function 'bool resigore(int, int)':
paint.cpp:79:51: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
         if(blocc == k+1)return dpgore[poz][blocc] = resenje;
                                ~~~~~~~~~~~~~~~~~~~^~~~~~~~~
paint.cpp:93:55: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
             if(blocc == k+1)return dpgore[poz][blocc] = 0;
                                    ~~~~~~~~~~~~~~~~~~~^~~
paint.cpp:103:31: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
     return dpgore[poz][blocc] = resenje;
            ~~~~~~~~~~~~~~~~~~~^~~~~~~~~

• 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