Submission #585887

#	Time	Username	Problem	Language	Result	Execution time	Memory
585887		georgievskiy	Paint By Numbers (IOI16_paint)	C++14	80 / 100	4 ms	852 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;

const int N = 110, K = 110;
bool d[N][K], w[N][K];
int cb[N], cw[N];
vector<int> c;

bool check(string s) {
    int n = s.size();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < (int)c.size(); j++)
            d[i][j] = w[i][j] = 0;
    cb[0] = s[0] == 'X', cw[0] = s[0] == '_';
    for (int i = 1; i < n; i++)
        cb[i] = cb[i - 1] + (s[i] == 'X'), cw[i] = cw[i - 1] + (s[i] == '_');

    for (int i = 0; i < n; i++) {
        int k0 = i - c[0];
        if (k0 >= 0)
            d[i][0] = cb[k0] == 0 && cw[i] - cw[k0] == 0;
        else if (k0 == -1)
            d[i][0] = cw[i] == 0;
        for (int j = 1; j < (int)c.size(); j++) {
            int k = i - c[j];
            if (k >= 0)
                d[i][j] = w[k][j - 1] && (cw[i] - cw[k] == 0);
        }
        if (s[i] == 'X' || i == 0)
            continue;
        for (int j = 0; j < (int)c.size(); j++)
            w[i][j] = w[i - 1][j] || d[i - 1][j];
    }
    for (int i = 0; i < n; i++)
        if (d[i][(int)c.size() - 1] && cb[n - 1] - cb[i] == 0)
            return 1;
    return 0;
}

string solve_puzzle(std::string s, std::vector<int> _c) {
    c = _c;
    string ans = s;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] != '.')
            continue;
        s[i] = 'X';
        bool tx = check(s);
        s[i] = '_';
        bool t_ = check(s);
        s[i] = '.';
        assert(tx || t_);
        if (tx && t_)
            ans[i] = '?';
        else if (tx)
            ans[i] = 'X';
        else
            ans[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