Submission #1021975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021975		mansur	Paint By Numbers (IOI16_paint)	C++17	100 / 100	189 ms	81956 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 + 1;
        if (i < n && s[i] == '_') r[i] = i;
    }
    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 (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;
        }
    }
    dp2[n][m][1] = 1;
    for (int i = n; i >= 1; i--) {
        for (int j = m; j >= 0; j--) {
            if (!dp2[i][j][0] && !dp2[i][j][1]) continue;
            if (s[i - 1] != 'X') dp2[i - 1][j][1] = 1;
            if (dp2[i][j][1] && j && i - c[j - 1] >= 0 && l[i - 1] < i - c[j - 1]) dp2[i - c[j - 1]][j - 1][0] = 1;
        }
    }
    int mx = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (r[i] >= i + c[j] && i + c[j] <= n) {
                if (dp1[i][j][1] && dp2[i + c[j]][j + 1][1]) mx = max(mx, i + c[j] - 1);
            }    
        }
        if (s[i] != '.') {
            ans += s[i];
            continue;
        }
        int y = 0;
        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 (mx >= i && y) ans += '?';
        else if (mx >= i) ans += 'X';
        else ans += '_';
    }
    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