Submission #1058939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058939		TAhmed33	Paint By Numbers (IOI16_paint)	C++98	90 / 100	2028 ms	21404 KiB

paint

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

using namespace std;

string solve_puzzle (string s, vector <int> c) {

    int n = s.length(), k = c.size();
    c.insert(c.begin(), 0);
    c.push_back(0);
    vector <vector <int>> p(2, vector <int> (n + 2, 0));
    vector <vector <int>> h(2, vector <int> (n + 2, 0));
    vector <vector <int>> f(k + 2, vector <int> (n + 2, 0));
    vector <vector <int>> g(k + 2, vector <int> (n + 2, 0));

    for (int i = 0; i < n; i++) {
        if (s[i] == '_') p[0][i + 1]++;
        if (s[i] == 'X') p[1][i + 1]++;
    }

    for (int i = 1; i <= n + 1; i++) {
        p[0][i] += p[0][i - 1];
        p[1][i] += p[1][i - 1];
    }

    f[0][0] = 1;

    for (int i = 1; i <= k; i++) {
        for (int j = c[i]; j <= n; j++) {  
            if (p[0][j] - p[0][j - c[i]] != 0) {
                continue;
            }
            if (j - c[i] == 0) {
                f[i][j] |= f[i - 1][0];
                continue;
            }
            for (int l = j - c[i]; l >= 1; l--) {
                if (p[1][j - c[i]] - p[1][l - 1] != 0) {
                    break;
                }
                f[i][j] |= f[i - 1][l - 1];
            }
        }
    }    

    g[k + 1][n + 1] = 1;

    for (int i = k; i >= 1; i--) {
        for (int j = n - c[i] + 1; j >= 1; j--) {
            if (p[0][j + c[i] - 1] - p[0][j - 1] != 0) {
                continue;
            }
            if (j + c[i] == n + 1) {
                g[i][j] |= g[i + 1][n + 1];
                continue;
            }
            for (int l = j + c[i]; l <= n; l++) {
                if (p[1][l] - p[1][j + c[i] - 1] != 0) {
                    break;
                }
                g[i][j] |= g[i + 1][l + 1];
            }
        }
    }

    for (int l = 0; l <= k; l++) {
        for (int i = 0; i <= n; i++) {
            for (int j = i + 2; j <= n + 1; j++) {
                if (f[l][i] && g[l + 1][j] && p[1][j - 1] - p[1][i] == 0) {
                    h[0][i + 1]++; h[0][j]--;
                    h[1][i - c[l] + 1]++; h[1][i + 1]--;
                    h[1][j]++; h[1][j + c[l + 1]]--;
                }
            }
        }
    }
    for (int i = 1; i <= n + 1; i++) {
        h[0][i] += h[0][i - 1];
        h[1][i] += h[1][i - 1];
    }
    string ans;
    for (int i = 1; i <= n; i++) {
        if (h[0][i] && h[1][i]) {
            ans.push_back('?');
        } else if (h[0][i]) {
            ans.push_back('_');
        } else {
            ans.push_back('X');
        }
    }
    return ans;
}

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