Submission #162179

#	Time	Username	Problem	Language	Result	Execution time	Memory
162179		popovicirobert	Paint By Numbers (IOI16_paint)	C++14	100 / 100	805 ms	43492 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = (int) 2e5 + 5;
const int MAXK = 100;

static bool dpl[MAXN + 1][MAXK + 1], dpr[MAXN + 1][MAXK + 1];
int toL[MAXN + 1];

inline void solve(string &str, vector <int> &c, int n, int k, bool dp[MAXN + 1][MAXK + 1]) {
    int i, j;
    for(i = 1; i <= n; i++) {
        toL[i] = i;
        if(str[i] != 'X') {
            toL[i] = toL[i - 1];
        }
    }

    vector <int> W(n + 1), sp(n + 1);

    dp[0][0] = 1;
    for(i = 1; i <= n; i++) {
        dp[i][0] = (dp[i - 1][0] && str[i] != 'X');
        W[i] = W[i - 1] + (str[i] == '_');
    }

    for(j = 1; j <= k; j++) {
        sp[0] = 0;
        for(i = 1; i <= n; i++) {
            if(i >= c[j] && str[i - c[j]] != 'X' && W[i] - W[i - c[j]] == 0) {
                if(j == 1) {
                    if(toL[i - c[j]] == 0)
                        dp[i][j] = 1;
                }
                else if(i > c[j]) {
                    dp[i][j] = (sp[i - c[j] - 1] - sp[max(0, toL[i - c[j]] - 1)] > 0);
                }
            }
            sp[i] = sp[i - 1] + dp[i][j - 1];
        }
    }
}

string solve_puzzle(string s, vector<int> c) {
    int n = s.size(), k = c.size();
    int i, j;

    string str = " " + s;
    c.resize(k + 1), str.resize(n + 2);
    for(i = k; i >= 1; i--) {
        c[i] = c[i - 1];
    }

    solve(str, c, n, k, dpl);
    for(i = 1; i < n - i + 1; i++) {
        swap(str[i], str[n - i + 1]);
    }
    for(i = 1; i < k - i + 1; i++) {
        swap(c[i], c[k - i + 1]);
    }

    solve(str, c, n, k, dpr);
    for(i = 1; i < n - i + 1; i++) {
        swap(str[i], str[n - i + 1]);
        for(j = 0; j <= k; j++) {
            swap(dpr[i][j], dpr[n - i + 1][j]);
        }
    }
    for(i = 1; i < k - i + 1; i++) {
        swap(c[i], c[k - i + 1]);
    }

    vector <int> B(n + 2), W(n + 2);

    for(j = 1; j <= k; j++) {
        int mx = n + 1, last = n + 1;
        for(i = n; i >= 1; i--) {
            /*if(i == 78 && j == 5) {
                cerr << mx << "\n";
            }*/
            if(dpl[i][j] && str[i + 1] != 'X' && ((j == k && last == n + 1) || (j < k && mx > i + 1 && mx != n + 1 && mx <= last))) {
                B[i - c[j] + 1]++;
                B[i + 1]--;

                W[i + 1]++;
                W[mx]--;
            }

            if(str[i] == 'X') last = i;

            if(dpr[i][k - j] && (mx > last || mx == n + 1) && j != k) {
                mx = i;
            }
        }
    }

    for(i = 1; i <= n; i++) {
        if(dpr[i][k]) {
            W[1]++, W[i]--;
        }
        if(str[i] == 'X') break;
    }

    string ans; ans.resize(n);
    for(i = 1; i <= n; i++) {
        B[i] += B[i - 1], W[i] += W[i - 1];
        if(B[i] && W[i]) {
            ans[i - 1] = '?';
        }
        else if(B[i]) {
            ans[i - 1] = 'X';
        }
        else if(W[i]) {
            ans[i - 1] = '_';
        }
        else {
            assert(0);
        }
    }

    return ans;
}

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