Submission #95228

#	Time	Username	Problem	Language	Result	Execution time	Memory
95228		someone_aa	Paint By Numbers (IOI16_paint)	C++17	32 / 100	2 ms	380 KiB

paint

#include "paint.h"

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

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

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

string code;

int cntwhite(int l, int r) {
    int cnt = 0;
    for(int i=l;i<=r;i++) {
        if(code[i] == '_') cnt++;
    }
    return cnt;
}


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

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

void setblack(int l, int r) {
    for(int i=l;i<=r;i++) {
        possible_black[i] = true;
    }
}

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

    code = s;

    dp[0][0] = true;


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

    for(int i=1;i<=n;i++) {
        for(int j=0;j<=m;j++) {
            dp[i][j] = dp[i-1][j];
            if(j == 0) continue;
            if(i - c[j-1] >= 0) {
                if(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++) {
            ds[i][j] = ds[i+1][j];
            if(j == 0) continue;
            if(i + rc[j-1] -1 <= n) {
                if(cntwhite(i, i+rc[j-1]-1) == 0) {
                    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++) {
        for(int j=1;j<=m;j++) {
            // check if you can start j-th clue at position i
            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) {
                                setblack(i, i+c[j-1]-1);
                                setwhite(i-1, i-1);
                                setwhite(i+c[j-1], i+c[j-1]);
                            }
                            else if(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]);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    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: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10