Submission #1044927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044927		Zicrus	Paint By Numbers (IOI16_paint)	C++17	80 / 100	7 ms	604 KiB

paint

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

typedef long long ll;

string solve(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 solveSub(string s, vector<int> c, ll n1, ll n, ll k1, ll k) {
    string orig = s;
    ll minLen = max(0ll, k-k1-1);
    for (int i = k1; i < k; i++) minLen += c[i];
    if (minLen > n-n1) return "-";
    vector<ll> blacks;
    for (int i = n1; i < n; i++) {
        if (s[i] == 'X') blacks.push_back(i);
    }
    blacks.push_back(n);
    ll m = blacks.size();
    if (minLen <= 0 && m > 1)
        return "-";
    else if (minLen <= 0) {
        for (int i = n1; i < n; i++) {
            s[i] = '_';
        }
        return s;
    }

    if (m == 1)
        return solve(s, c, n1, n, k1, k);

    ll play = n-n1 - minLen;
    vector<ll> cOff(k-k1);
    for (int i = 1; i < k-k1; i++) {
        cOff[i] = cOff[i-1] + c[i+k1-1] + 1;
    }
    unordered_set<ll> idk;
    bool has = false;
    ll pos = n1;
    ll curC = k-k1-1;
    ll mid = (m-1)/2;
    while (pos <= n1+play) {
        while (curC >= 0 && cOff[curC] + pos > blacks[mid]) curC--;
        if (curC < 0) break;
        if (cOff[curC] + pos + c[curC+k1] <= blacks[mid]) { pos++; continue; }
        ll low = cOff[curC] + pos;
        ll high = low + c[curC+k1];
        ll kL = curC;
        ll kH = k-k1 - curC - 1;
        ll hash = low | (high << 7) | (kL << 14) | (kH << 21);
        idk.insert(hash);
        has = true;
        pos++;
    }
    if (!has)
        return "-";

    /*vector<vector<bool>> poss(m, vector<bool>(k-k1+1));
    vector<vector<string>> dp(m, vector<string>(k-k1+1));
    for (int i = 0; i < m; i++) {
        poss[i][0] = true;
        dp[i][0] = s;
        for (int j = n1; j < blacks[i]; j++) {
            dp[i][0][j] = '_';
        }
    }
    for (int j = k1+1; j <= k && poss[0][j-1]; j++) {
        dp[0][j] = solve(s, c, n1, blacks[0], k1, j);
        poss[0][j] = dp[0][j][0] != '-';
    }*/
    string dummy = "";
    bool f = false;
    for (int i = 0; i < n; i++) dummy += s[i];
    for (auto &e : idk) {
        ll low = e & 127;
        ll high = (e >> 7) & 127;
        bool lo = low > n1, hi = high < n;
        if (lo) low--;
        if (hi) high++;
        ll kL = (e >> 14) & 127;
        ll kH = (e >> 21) & 127;
        string sol = solveSub(dummy, c, n1, low, k1, k1+kL);
        if (sol[0] == '-') continue;
        sol = solveSub(sol, c, high, n, k-kH, k);
        if (sol[0] == '-') continue;
        if (lo) {
            if (sol[low] == 'X') continue;
            sol[low] = '_';
        }
        if (hi) {
            if (sol[high-1] == 'X') continue;
            sol[high-1] = '_';
        }
        for (int i1 = low+lo; i1 < high-hi; i1++) {
            sol[i1] = 'X';
        }
        for (int i1 = n1; i1 < high; i1++) {
            if (s[i1] == '.') s[i1] = sol[i1];
            else if (sol[i1] == '?' || sol[i1] != s[i1]) s[i1] = '?';
        }
        for (int i1 = high; i1 < n; i1++) {
            if (s[i1] == '.') s[i1] = sol[i1];
            else if (sol[i1] == '?' || sol[i1] != s[i1]) s[i1] = '?';
        }
        f = true;
    }

    for (int i = n1; i < n; i++) {
        if (orig[i] == s[i]) continue;
        if (orig[i] == 'X')
            s[i] = 'X';
        if (orig[i] == '_')
            s[i] = '_';
    }
    return f ? 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++) {
        dp[i][0] = solveSub(s, c, 0, spaces[i], 0, 0);
        poss[i][0] = dp[i][0][0] != '-';
    }
    for (int j = 1; j <= k; 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; 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: 21 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10