Submission #1009909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009909		overwatch9	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	2452 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
using namespace std;
string s;
vector <int> c;
int n, m;
const int maxnk = 101;
bool ready[maxnk][maxnk][maxnk];
bool dp[maxnk][maxnk][maxnk];
bool solve(int len, int i, int j) {
    if (len < -1)
        return false;
    if (len <= 0) {
        return i > j;
    }
    if (i > j)
        return true;
    if (ready[len][i][j])
        return dp[len][i][j];
    bool ans = solve(len - c[i] - 1, i+1, j);
    ans |= solve(len - 1, i, j);
    dp[len][i][j] = ans;
    ready[len][i][j] = true;
    return ans;
}
string solve_puzzle(string S, vector<int> C) {
    s = S;
    c = C;
    n = S.size();
    m = c.size();
    string ans;
    ans.resize(n, '?');
    int pt = 0;
    int len = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '.')
            len++;
        else {
            int x = 0, len2 = 0;
            while (pt < m && len2 + C[pt] <= len) {
                len2 += C[pt];
                pt++;
                x++;
                len2++;
            }
            vector <vector <int>> st(2);
            int cur = 1;
            int prev = 0;
            for (int j = 0; j < len; j++)
                st[prev].push_back(n - j - 1);
            for (int j = pt - x; j < pt; j++) {
                st[cur].clear();
                for (auto k : st[prev]) {
                    if (solve(n - k, j, pt-1))
                        st[cur].push_back(k + C[j] + 1);
                }
                if ((int)st[cur].size() == 1) {
                    for (int k = 1; k <= C[j]; k++)
                        ans[st[cur].back() - k - 1] = 'X';
                    if (j+1 < pt && st[cur].back() - 1 < n)
                        ans[st[cur].back() - 1] = '_';
                } else if ((int)st[cur].size() > 1 && C[j] > 1) {
                    for (int k = 0; k < C[j] - (int)st[cur].size() + 1; k++)
                        ans[st[cur][0] - C[j] - 1 + k] = 'X';
                }
                swap(prev, cur);
            }
        }
    }
    if (len > 0) {
        int x = 0, len2 = 0;
        while (pt < m && len2 + C[pt] <= len) {
            len2 += C[pt];
            pt++;
            x++;
            len2++;
        }
        vector <vector <int>> st(2);
        int cur = 1;
        int prev = 0;
        for (int j = 0; j < len; j++)
            st[prev].push_back(n - j - 1);
        for (int j = pt - x; j < pt; j++) {
            st[cur].clear();
            for (auto k : st[prev]) {
                if (solve(n - k, j, pt-1))
                    st[cur].push_back(k + C[j] + 1);
            }
            if ((int)st[cur].size() == 1) {
                for (int k = 1; k <= C[j]; k++)
                    ans[st[cur].back() - k - 1] = 'X';
                if (j+1 < pt && st[cur].back() - 1 < n)
                    ans[st[cur].back() - 1] = '_';
            } else if ((int)st[cur].size() > 1 && C[j] > 1) {
                for (int k = 0; k < C[j] - (int)st[cur].size() + 1; k++)
                    ans[st[cur][0] - C[j] - 1 + k] = 'X';
            }
            swap(prev, cur);
        }
    }
    return ans;
}
// int main() {
//     string tp;
//     cin >> tp;
//     int clen;
//     cin >> clen;
//     vector <int> c(clen);
//     for (int i = 0; i < clen; i++)
//         cin >> c[i];
//     cout << solve_puzzle(tp, c) << '\n';
// }

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