Submission #730368

#	Time	Username	Problem	Language	Result	Execution time	Memory
730368		vjudge1	Paint By Numbers (IOI16_paint)	C++11	100 / 100	297 ms	44024 KiB

paint

#include "paint.h"

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

int N, K;
bool f[101][200004], g[101][200004];
int ps[2][200004];
int ok[2][200004];

std::string solve_puzzle(std::string s, std::vector<int> c) {
        N = s.size();
        s = "__" + s + "__";
        K = c.size();
        f[0][0] = f[0][1] = g[0][N + 2] = g[0][N + 3] = 1;
        for (int i = 2; i <= N + 1; i++) ps[0][i] = ps[0][i - 1] + (s[i] == '_');
        for (int i = 2; i <= N + 1; i++) ps[1][i] = ps[1][i - 1] + (s[i] == 'X');
        for (int i = 2; i <= N + 1; i++) {
                for (int j = 0; j <= K; j++) {
                        if (s[i] == 'X' || s[i] == '.') {
                                if (j > 0 && i - 1 >= c[j - 1] && ps[0][i] - ps[0][i - c[j - 1]] == 0 && s[i - c[j - 1]] != 'X' && s[i + 1] != 'X') {
                                        f[j][i] |= f[j - 1][i - c[j - 1] - 1];
                                }
                        }
                        if (s[i] == '_' || s[i] == '.') {
                                f[j][i] |= f[j][i - 1];
                        }
                }
        }
        reverse(c.begin(), c.end());
        for (int i = N + 1; i >= 2; i--) {
                for (int j = 0; j <= K; j++) {
                        if (s[i] == 'X' || s[i] == '.') {
                                if (j > 0 && i + c[j - 1] - 1 <= N + 1 && ps[0][i + c[j - 1] - 1] - ps[0][i - 1] == 0 && s[i + c[j - 1]] != 'X' && s[i - 1] != 'X') {
                                        g[j][i] |= g[j - 1][i + c[j - 1] + 1];
                                }
                        }
                        if (s[i] == '_' || s[i] == '.') {
                                g[j][i] |= g[j][i + 1];
                        }
                }
        }
        reverse(c.begin(), c.end());
        for (int i = 2; i <= N + 1; i++) {
                for (int j = 0; j <= K; j++) {
                        if (s[i] == 'X') continue;
                        if (f[j][i - 1] && g[K - j][i + 1]) ok[0][i] = 1;
                }
        }
        for (int j = 1; j <= K; j++) {
                for (int i = c[j - 1] + 1; i <= N + 1; i++) {
                        if (ps[0][i] - ps[0][i - c[j - 1]]) continue;
                        if (s[i + 1] == 'X') continue;
                        if (s[i - c[j - 1]] == 'X') continue;
                        if (f[j - 1][i - c[j - 1] - 1] && g[K - j][i + 2]) ok[1][i - c[j - 1] + 1]++, ok[1][i + 1]--;
                }
        }
        for (int i = 1; i <= N + 1; i++) ok[1][i] += ok[1][i - 1];
        string ans(N, '?');
        for (int i = 2; i <= N + 1; i++) {
                if (ok[1][i]) ans[i - 2] = 'X';
                if (ok[0][i]) ans[i - 2] = '_';
                if (ok[1][i] && ok[0][i]) ans[i - 2] = '?';
        }
        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: 10 / 10