Submission #1021784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021784		vjudge1	Paint By Numbers (IOI16_paint)	C++17	80 / 100	2063 ms	137044 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>;

int can(string &s, vector<int> &c) {
    int n = sz(s), m = sz(c);
    bool dp[n + 2][m + 1][n + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            if (j == m) {
                if (dp[i][j][0] && s[i] != 'X') dp[i + 1][j][0] = 1;
                continue;
            }
            for (int k = 0; k <= c[j]; k++) {
                //cout << dp[i][j][k] << ' ';
                if (!dp[i][j][k]) continue;
                if (k) {
                    if (k == c[j]) {
                        if (s[i] != 'X') dp[i + 1][j + 1][0] = 1;
                        continue;
                    }
                    if (s[i] != '_') dp[i + 1][j][k + 1] = 1;
                    continue;
                }
                if (s[i] != '_') dp[i + 1][j][1] = 1;
                if (s[i] != 'X') dp[i + 1][j][0] = 1;
            }
            //cout << endl;
        }
        //cout << endl << endl;
    }
    return (dp[n][m][0] || dp[n][m - 1][c[m - 1]]);
}

string solve_puzzle(string s, vector<int> c) {
    string ans = "";
    int n = sz(s);
    for (int i = 0; i < n; i++) {
        if (s[i] != '.') {
            ans += s[i];
            continue;
        }
        s[i] = '_';
        int x = can(s, c);
        s[i] = 'X';
        int y = can(s, c);
        //cout << i << ' ' << x << ' ' << y << endl;
        if (x && y) ans += '?';
        else if (x) ans += '_';
        else ans += 'X';
        s[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