Submission #581564

#	Time	Username	Problem	Language	Result	Execution time	Memory
581564		SlavicG	Paint By Numbers (IOI16_paint)	C++17	80 / 100	2065 ms	832 KiB

paint

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

#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(),a.end()
using ll = long long;
using namespace std;

int query(int l, int r, vector<int>& p) {
    assert(l >= 0 && r >= 0 && l < sz(p) && r < sz(p));
    assert(l <= r);
    return p[r] - (l ? p[l - 1]: 0);
}

bool calc(string s, vector<int> c) {
    int n = sz(s), k = sz(c);
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    vector<int> black(n + 1, 0), white(n + 1, 0);
    dp[0][0] = 1;
    for(int i = 0; i < n; ++i) {
        black[i + 1] = black[i] + (s[i] == 'X');
        white[i + 1] = white[i] + (s[i] == '_');
        if(!black[i + 1]) dp[i + 1][0] = 1;
    }

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= k; ++j) {
            if(s[i - 1] == 'X' || s[i - 1] == '.') {
                int p = i - c[j - 1];
                if(p - (j != 1) < 0 || query(p + 1, i, white) || query(p, p, black)) {
                    //Purice Chad
                } else dp[i][j] |= dp[p - (j != 1)][j - 1];
            }
            if(s[i - 1] == '_' || s[i - 1] == '.') {
                dp[i][j] |= dp[i - 1][j];
            }
        }
    }
    return dp[n][k];
}

string solve_puzzle(string s, vector<int> c) {
    string ans = "";
    int n = sz(s);
    for(int i = 0; i < n; ++i) {
        if(s[i] == 'X') {
            ans += 'X';
        } else if(s[i] == '_') {
            ans += '_';
        } else {
            s[i] = 'X';
            bool ok1 = calc(s, c);
            s[i] = '_';
            bool ok2 = calc(s, c);
            assert(ok1 || ok2);
            if(ok1 && ok2) {
                ans += '?';
            } else if(ok1) {
                ans += 'X';
            } else {
                ans += '_';
            }
            s[i] = '.';
        }
    }
    return ans;
}

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