Submission #428054

#	Time	Username	Problem	Language	Result	Execution time	Memory
428054		dxz05	Paint By Numbers (IOI16_paint)	C++14	0 / 100	1 ms	204 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5600;

bool dp[N][101], pdp[N];
int pw[N], pb[N];

int getw(int l, int r){
    if (l > r) return 0;
    return pw[r] - (l > 0 ? pw[l - 1] : 0);
}

int getb(int l, int r){
    if (l > r) return 0;
    return pb[r] - (l > 0 ? pb[l - 1] : 0);
}

bool check(string &s, vector<int> &c){
    int n = s.size(), k = c.size();

    for (int i = 0; i < n; i++){
        pb[i] = s[i] == 'X';
        pw[i] = s[i] == '_';
        if (i > 0) pb[i] += pb[i - 1], pw[i] += pw[i - 1];
    }

    for (int i = 0; i < k; i++){
        for (int j = 0; j < n; j++){
            if (j + 1 < c[i]){
                dp[i][j] = false;
                continue;
            }
            int l = j - c[i] + 1;
            if (j < n - 1 && s[j + 1] == 'X' || l > 0 && s[l - 1] == 'X' || getw(l, j) > 0){
                dp[i][j] = false;
                continue;
            }

            if (i == 0){
                dp[i][j] = getb(0, l - 1) == 0;
            } else
                if (l >= 2) dp[i][j] = pdp[l - 2]; else
                    dp[i][j] = false;
        }

        for (int j = 0; j < n; j++){
            pdp[j] = dp[i][j];
            if (j) pdp[j] |= pdp[j - 1];
        }

    }

    if (false){
        cout << s << endl;
        for (int i = 0; i < k; i++){
            for (int j = 0; j < n; j++){
                cout << dp[i][j] << ' ';
            }
            cout << endl;
        }
        cout << endl;
    }

    for (int i = n - 1; i >= 0; i--){
        if (dp[k - 1][i]) return true;
        if (s[i] == 'X') break;
    }
    return false;
}

string solve_puzzle(string s, vector<int> c) {
    int n = s.size();
    string ans(n, 'Y');
    for (int i = 0; i < n; i++){
        if (s[i] != '.'){
            ans[i] = s[i];
            continue;
        }

        s[i] = 'X';
        bool black = check(s, c);
        s[i] = '_';
        bool white = check(s, c);
        s[i] = '.';

        if (black && !white) ans[i] = 'X';
        if (!black && white) ans[i] = '_';
        if (black && white) ans[i] = '?';

        cout << black << ' ' << white << endl;
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool check(std::string&, std::vector<int>&)':
paint.cpp:37:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   37 |             if (j < n - 1 && s[j + 1] == 'X' || l > 0 && s[l - 1] == 'X' || getw(l, j) > 0){
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~~~~~

• 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