Submission #1021877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021877		mansur	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	604 KiB

paint

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

using namespace std;

#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second 
#define f first   

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int N = 2e5 + 5;

bool dp1[N][101][2], dp2[N][101][2];

string solve_puzzle(string s, vector<int> c) {
    string ans = "";
    int n = sz(s), m = sz(c);
    int l[n + 1], r[n + 1];
    for (int i = 0; i <= n; i++) {
        if (i) l[i] = l[i - 1];
        else l[i] = -1;
        if (i < n && s[i] == '_') l[i] = i;
    }
    for (int i = n; i >= 0; i--) {
        if (i < n - 1) r[i] = r[i + 1];
        else r[i] = n;
        if (i < n && s[i] == '_') r[i] = i;
    }
    int l1[n + 1], r1[n + 1];
    for (int i = 0; i <= n; i++) {
        if (i) l1[i] = l1[i - 1];
        else l1[i] = -1;
        if (i < n && s[i] == 'X') l1[i] = i;
    }
    for (int i = n; i >= 0; i--) {
        if (i < n) r1[i] = r1[i + 1];
        else r1[i] = n;
        if (i < n && s[i] == 'X') r1[i] = i;
    }
    vector<int> posl(m + 1, n + 1);
    dp1[0][0][1] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            if (!dp1[i][j][0] && !dp1[i][j][1]) continue;
            if (dp1[i][j][0]) posl[j] = min(posl[j], i + 1);
            if (dp1[i][j][1]) posl[j] = min(posl[j], i);
            if (s[i] != 'X') dp1[i + 1][j][1] = 1;
            if (dp1[i][j][1] && j < m && i + c[j] <= n && r[i] >= i + c[j]) dp1[i + c[j]][j + 1][0] = 1;
        }
    }
    vector<int> posr(m + 1, -1);
    dp2[n][m][1] = 1;
    for (int i = n; i >= 1; i--) {
        for (int j = m; j >= 0; j--) {
            //cout << dp2[i][j][0] << ' ' << dp2[i][j][1] << ' ' << l[i] << "  ";
            if (!dp2[i][j][0] && !dp2[i][j][1]) continue;
            if (dp2[i][j][0]) {
                posr[j] = max(posr[j], i - 2);
            }
            if (dp2[i][j][1]) posr[j] = max(posr[j], i - 1);
            if (s[i - 1] != 'X') dp2[i - 1][j][1] = 1;
            if (dp2[i][j][1] && j && i - c[j - 1] >= 0 && l[i] < i - c[j - 1]) dp2[i - c[j - 1]][j - 1][0] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        if (s[i] != '.') {
            ans += s[i];
            continue;
        }
        int x = 0, y = 0;
        for (int j = 0; j < m; j++) {
            int tl = max(posl[j], l[i] + 1);
            int tr = min(posr[j + 1], r[i] - 1);
            if (tl <= i && i <= tr && tr - tl + 1 >= c[j]) {
                tl = min(r1[tl], i);
                tr = max(l1[tr], i);
                if (tr - tl + 1 <= c[j]) x = 1;
            }
        }
        for (int j = 0; j <= m; j++) {
            if ((dp1[i][j][0] || dp1[i][j][1]) && (dp2[i + 1][j][0] || dp2[i + 1][j][1])) y = 1;
        }
        if (x && y) ans += '?';
        else if (x) ans += 'X';
        else ans += '_';
    }
    return ans;
}
 

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