Submission #428293

#	Time	Username	Problem	Language	Result	Execution time	Memory
428293		dxz05	Paint By Numbers (IOI16_paint)	C++14	10 / 100	2069 ms	308 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++){
            dp[i][j] = false;

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

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

        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 stress(string &s, vector<int> &c);

string solve_puzzle(string s, vector<int> c) {
    return stress(s, 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;
}

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

    vector<int> v(n, 0);

    for (int mask = 0; mask < (1 << n); mask++){
        string t;
        bool ok = true;
        for (int i = 0; i < n; i++){
            t += ((mask & (1 << i)) ? 'X' : '_');
            if (s[i] != '.' && s[i] != t[i]) {
                ok = false;
                break;
            }
        }

        int j = 0;
        for (int i = 0; i < n; i++){
            if (t[i] == '_') continue;

            int r = i;
            while (r < n && t[r] == 'X') r++;
            r--;

            if (j >= k || r - i + 1 != c[j++]){
                ok = false;
                break;
            }

            i = r;
        }

        if (!ok || j != k) continue;

        for (int i = 0; i < n; i++){
            v[i] |= (t[i] == '_' ? 1 : 2);
        }

        //cout << t << endl;

    }

    string res;
    for (int x : v){
        res += (x == 1 ? '_' : x == 2 ? 'X' : '?');
    }

    return res;
}

Compilation message (stderr)

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

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