Submission #1044594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044594		Zicrus	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	348 KiB

paint

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

typedef long long ll;

string solveSub(string s, vector<int> c, ll n1, ll n, ll k1, ll k) {
    ll minLen = k-k1-1;
    for (int i = k1; i < k; i++) minLen += c[i];
    if (minLen > n-n1) return "-";

    if (minLen <= 0) {
        for (int i = n1; i < n; i++) {
            s[i] = '_';
        }
        return s;
    }

    ll play = n-n1 - minLen;
    ll pos = n1;
    for (int i = k1; i < k; i++) {
        for (int j = pos+play; j < pos+c[i]; j++) {
            s[j] = 'X';
        }
        pos += c[i]+1;
    }
    for (int i = n1; i < n; i++) {
        if (s[i] == '.') s[i] = minLen == n-n1 ? '_' : '?';
    }

    return s;
}

string solve_puzzle(string s, vector<int> c) {
    ll n = s.size(), k = c.size();
    vector<ll> spaces;
    for (int i = 0; i < n; i++) {
        if (s[i] == '_') spaces.push_back(i);
    }
    spaces.push_back(n);
    ll m = spaces.size();
    vector<vector<bool>> poss(m, vector<bool>(k+1));
    vector<vector<string>> dp(m, vector<string>(k+1));
    for (int i = 0; i < m; i++) {
        poss[i][0] = true;
        dp[i][0] = s;
        for (int j = 0; j < spaces[i]; j++) {
            dp[i][0][j] = '_';
        }
    }
    for (int j = 1; j <= k && poss[0][j-1]; j++) {
        dp[0][j] = solveSub(s, c, 0, spaces[0], 0, j);
        poss[0][j] = dp[0][j][0] != '-';
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j <= k && poss[i][j-1]; j++) {
            for (int p = 0; p <= j; p++) {
                if (!poss[i-1][p]) continue;
                string sol = solveSub(s, c, spaces[i-1]+1, spaces[i], p, j);
                bool valid = sol[0] != '-';
                if (valid) {
                    if (!poss[i][j]) {
                        dp[i][j] = dp[i-1][p];
                        for (int i1 = spaces[i-1]+1; i1 < spaces[i]; i1++) {
                            dp[i][j][i1] = sol[i1];
                        }
                        poss[i][j] = true;
                    }
                    else {
                        for (int i1 = 0; i1 < spaces[i-1]; i1++) {
                            if (dp[i-1][p][i1] == '?' || dp[i-1][p][i1] != dp[i][j][i1]) dp[i][j][i1] = '?';
                        }
                        for (int i1 = spaces[i-1]+1; i1 < spaces[i]; i1++) {
                            if (sol[i1] == '?' || sol[i1] != dp[i][j][i1]) dp[i][j][i1] = '?';
                        }
                    }
                }
            }
        }
    }

    return dp[m-1][k];
}

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