Submission #770088

#	Time	Username	Problem	Language	Result	Execution time	Memory
770088		meowmeow	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	852 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
using namespace std;
int p0[200001], p1[200001];
int dp[101][200001];
int dp2[101][200001];
int bl[200001];
void solve_row(string &s, int m, vector<int> r, int k) {
    p0[0] = 0, p1[0] = 0;
    for(int i = 0; i < m; i++) {
        bl[i] = 0;
        p0[i+1] = p0[i];
        p1[i+1] = p1[i];
        if (s[i] == '_') {
            p0[i+1]++;
        } else if (s[i] == 'X') {
            p1[i+1]++;
        }
    }
    dp[0][0] = 1;
    for (int j = 1; j <= m; j++) {
        if (s[j-1] != 'X') dp[0][j] = dp[0][j-1];
        else dp[0][j] = 0;
    }
    for (int i = 1; i <= k; i++) {
        dp[i][0] = 0;
        for (int j = 1; j <= m; j++) {
            if (s[j-1] == '_') {
                dp[i][j] = dp[i][j-1];
            } else {
                int te = 0;
                if (j >= r[i-1] && p0[j] == p0[j-r[i-1]]) {
                    if (j == r[i-1]) {
                        te = dp[i-1][0];
                    } else {
                        te = dp[i-1][j-r[i-1]-1];
                    }
                }
                if (s[j-1] == 'X') {
                    dp[i][j] = te;
                } else {
                    dp[i][j] = te || dp[i][j-1];
                }
            }
        }
    }
    dp2[k][m] = 1;
    for (int j = m-1; j >= 0; j--) {
        if (s[j] != 'X') dp2[k][j] = dp2[k][j+1];
        else dp2[k][j] = 0;
    }
    for (int i = k-1; i >= 0; i--) {
        dp2[i][m] = 0;
        for (int j = m-1; j >= 0; j--) {
            if (s[j] == '_') {
                dp2[i][j] = dp2[i][j+1];
            } else {
                int te = 0;
                if (m-j >= r[i] && p0[j] == p0[j+r[i]]) {
                    if (m-j == r[i]) {
                        te = dp2[i+1][m];
                    } else {
                        te = dp2[i+1][j+r[i]+1];
                    }
                }
                if (s[j] == 'X') {
                    dp2[i][j] = te;
                } else {
                    dp2[i][j] = te || dp2[i][j+1];
                }
            }
        }
    }
    for (int i = 0; i < k; i++) {
        for (int j = 0; j <= m-r[i]; j++) {
            if ((j == 0 || s[j-1] != 'X') && (j == m-r[i] || s[j+r[i]] != 'X') && p0[j+r[i]] == p0[j] && ((j == 0 && dp[i][j]) || (j > 0 && dp[i][j-1])) && ((j+r[i] == m && dp2[i+1][j+r[i]]) || (j+r[i] < m && dp2[i+1][j+r[i]+1]))) {
                bl[j] = max(bl[j], r[i]);
            }
        }
    }
    int bb = 0;
    for (int j = 0; j < m; j++) {
        int w = 0;
        if (s[j] != 'X') {
            for (int i = 0; i <= k; i++) {
                if (dp[i][j] && dp2[i][j+1]) {
                    w = 1;
                    break;
                }
            }
        }
        bb = max(bb, bl[j]);
        //cout << w << '.' << bb << ' ';
        if (w) {
            if (!bb) {
                s[j] = '_';
            } else {
                s[j] = '?';
            }
        } else if (bb) {
            s[j] = 'X';
        } else {
            s[j] = '?';
        }
        bb = max(0, bb - 1);
    }
    /*cout<<'\n';
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j <= m; j++) cout << dp[i][j] << ' ';
        cout << '\n';
    }
    cout<<'\n';
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j <= m; j++) cout << dp2[i][j] << ' ';
        cout << '\n';
    }*/
}
string solve_puzzle(string s, vector<int> c) {
    string t = s;
    solve_row(t, t.length(), c, c.size());
    return t;
}

• 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