Submission #95235

#	Time	Username	Problem	Language	Result	Execution time	Memory
95235		someone_aa	Paint By Numbers (IOI16_paint)	C++17	100 / 100	368 ms	47572 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <bits/stdc++.h>

using namespace std;
const int maxn = 200100;
const int maxm = 110;
int n, m;

bool dp[maxn][maxm];
bool ds[maxn][maxm];

string code;

int prefwhite[maxn];
int prefblack[maxn];

int cntwhite(int l, int r) {
    return prefwhite[r] - prefwhite[l-1];
}


bool possible_white[maxn];
bool possible_black[maxn];

int marker_black[maxn];

void setwhite(int l, int r) {
    possible_white[l] = true;
}

void setblack(int l, int r) {
    marker_black[l]++;
    marker_black[r+1]--;
}

string solve_puzzle(string s, vector<int> c) {
    n = s.length();
    m = c.size();
    s = "$" + s + "$";

    code = s;

    vector<int> rc = c;
    reverse(rc.begin(), rc.end());

    for(int i=1;i<=n;i++) {
        prefwhite[i] = prefwhite[i-1];
        prefblack[i] = prefblack[i-1];

        if(s[i] == '_') prefwhite[i]++;
        else if(s[i] == 'X') prefblack[i]++;
    }

    dp[0][0] = true;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=m;j++) {

            if(j == 0) {
                if(s[i] != 'X') dp[i][j] = dp[i-1][j];
                continue;
            }



            if(s[i] == '_' || s[i] == '.') {
                dp[i][j] = dp[i-1][j];
            }

            if(s[i] == 'X' || s[i] == '.') {
                if(i - c[j-1] >= 0) {
                    if(s[i+1] != 'X' && s[i-c[j-1]] != 'X' && cntwhite(i-c[j-1]+1, i) == 0) {
                        if(j == 1)
                            dp[i][j] |= dp[i-c[j-1]][j-1];
                        else
                            dp[i][j] |= dp[i-c[j-1]-1][j-1];
                    }
                }
            }
            //cout<<"("<<i<<", "<<j<<") -> "<<dp[i][j]<<"\n";
        }
    }

    ds[n+1][0] = true;
    for(int i=n;i>=1;i--) {
        for(int j=0;j<=m;j++) {

            if(j == 0) {
                if(s[i] != 'X') ds[i][j] = ds[i+1][j];
                continue;
            }


            if(s[i] == '_' || s[i] == '.') {
                ds[i][j] = ds[i+1][j];
            }

            if(s[i] == 'X' || s[i] == '.') {
                if(i + rc[j-1] -1 <= n) {
                    if(s[i-1] != 'X' && s[i+rc[j-1]] != 'X' && cntwhite(i, i+rc[j-1]-1) == 0) {
                        //cout<<"Ulaza -> "<<i<<"\n";
                        if(j == 1) {
                            ds[i][j] |= ds[i+rc[j-1]][j-1];
                        }
                        else {
                            ds[i][j] |= ds[i+rc[j-1]+1][j-1];
                        }
                    }
                }
            }
            //cout<<i<<", "<<j<<" -> "<<ds[i][j]<<"\n";

        }
    }

    for(int i=1;i<=n;i++) {
        bool save = false;
        for(int j=1;j<=m;j++) {
            // check if you can start j-th clue at position i

            if(dp[i-1][j] && ds[i+1][m-j]) {
                save = true;
            }

            if(i + c[j-1] - 1 <= n) {
                if(s[i-1] != 'X' && s[i+c[j-1]] != 'X') {
                    if(cntwhite(i, i+c[j-1]-1) == 0) {
                        if(j == 1) {
                            if(i + c[j-1] - 1 == n && j == m && dp[i-1][0]) {
                                setblack(i, i+c[j-1]-1);
                                setwhite(i-1, i-1);
                                setwhite(i+c[j-1], i+c[j-1]);
                            }
                            else if(dp[i-1][0] && ds[i+c[j-1]+1][m-j]) {
                                setblack(i, i+c[j-1]-1);
                                setwhite(i-1, i-1);
                                setwhite(i+c[j-1], i+c[j-1]);
                            }
                        }
                        else if(i >= 2){
                            if(j == m) {
                                if(dp[i-2][j-1] && ds[i+c[j-1]][m-j]) {
                                    //cout<<"Setting last at: "<<i<<"\n";
                                    setblack(i, i+c[j-1]-1);
                                    setwhite(i-1, i-1);
                                    setwhite(i+c[j-1], i+c[j-1]);
                                }
                            }
                            else {
                                if(dp[i-2][j-1] && ds[i+c[j-1]+1][m-j]) {
                                    //cout<<"Setting: "<<j<<" at "<<i<<"\n";
                                    setblack(i, i+c[j-1]-1);
                                    setwhite(i-1, i-1);
                                    setwhite(i+c[j-1], i+c[j-1]);
                                }
                            }
                        }
                    }
                }
            }
        }

        if(dp[i-1][0] && ds[i+1][m]) save = true;

        if(save) {
            setwhite(i, i);
        }

    }

    int cnt = 0;
    for(int i=1;i<=n;i++) {
        cnt += marker_black[i];
        if(cnt > 0) possible_black[i] = true;
    }

    string result = "";
    for(int i=1;i<=n;i++) {
        if(s[i] == '.') {
            if(possible_black[i]) {
                if(possible_white[i]) result += "?";
                else 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