Submission #1044704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044704		Zicrus	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	444 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) {
    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;
    }
    vector<unordered_set<ll>> idk(m);
    for (int i = 0; i < m; i++) {
        ll pos = n1;
        ll curC = k-k1-1;
        while (pos <= n1+play) {
            while (curC >= 0 && cOff[curC] + pos > blacks[i]) curC--;
            if (curC < 0) break;
            if (cOff[curC] + pos + c[curC] <= blacks[i]) { pos++; continue; }
            ll low = cOff[curC] + pos;
            ll high = low + c[curC];
            ll kL = curC;
            ll kH = k-k1 - curC - 1;
            ll hash = low | (high << 8) | (kL << 16) | (kH << 24);
            idk[i].insert(hash);
            pos++;
        }
    }

    /*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 = "";
    for (int i = 0; i < n; i++) dummy += s[i];
    for (int i = 0; i < m; i++) {
        for (auto &e : idk[i]) {
            ll low = e & 255;
            ll high = (e >> 8) & 255;
            ll kL = (e >> 16) & 255;
            ll kH = (e >> 24) & 255;
            string sol = solveSub(dummy, c, n1, low, k1, kL);
            for (int i1 = low; i1 < high; 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] = '?';
            }
            sol = solveSub(dummy, c, high, n, k-kH, k);
            for (int i1 = high; i1 < n; i1++) {
                if (s[i1] == '.') s[i1] = sol[i1];
                else if (sol[i1] == '?' || sol[i1] != s[i1]) s[i1] = '?';
            }
        }
    }

    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