Submission #779064

#	Time	Username	Problem	Language	Result	Execution time	Memory
779064		vjudge1	Paint By Numbers (IOI16_paint)	C++17	100 / 100	791 ms	409596 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define sp " "
#define N 200005
#define K 105

int dp[N][K][2], dp2[N][K][2];
int pre_one[K][N];

string solve_puzzle(string s, vector<int> c) {
    int n = s.size();
    int k = c.size();
    vector<int> tmp;
    tmp.pb(0);
    for (auto i : c) tmp.pb(i);
    c = tmp;

    string t = ".";
    t = t + s;
    s = t;

    vector<int> pre(n + 5, 0);

    for (int i = 1; i <= n; i++)
    {
        pre[i] = pre[i - 1];
        if (s[i] == '_') pre[i]++;
    }

    dp[n + 1][k + 1][0] = 1;

    for (int i = n; i >= 1; i--){
        for (int j = 1; j <= k + 1; j++){
            if (s[i] == 'X'){
                dp[i][j][0] = 0;

                if (j == k + 1 || c[j] + i - 1 > n) 
                    dp[i][j][1] = 0;
                else 
                {
                    int p = pre[i + c[j] - 1] - pre[i - 1];
                    dp[i][j][1] = (dp[i + c[j]][j + 1][0]) & (p == 0);
                }
            }
            else if (s[i] == '_'){
                dp[i][j][1] = 0;
                dp[i][j][0] = dp[i + 1][j][0] | dp[i + 1][j][1];
            }
            else{
                dp[i][j][0] = dp[i + 1][j][0] | dp[i + 1][j][1];

                 if (j == k + 1 || c[j] + i - 1 > n) 
                    dp[i][j][1] = 0;
                else {
                    int p = pre[i + c[j] - 1] - pre[i - 1];
                    dp[i][j][1] = (dp[i + c[j]][j + 1][0]) & (p == 0);
                }
            }
            //cout<<i<<sp<<j<<" : "<<dp[i][j][0]<<sp<<dp[i][j][1]<<endl;
        }
    }

    dp2[0][0][0] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= k; j++){
            if (s[i] == 'X'){
                dp2[i][j][0] = 0;
                if (j == 0 || i < c[j]) dp2[i][j][1] = 0;
                else{
                    int p = pre[i] - pre[i - c[j]];
                    dp2[i][j][1] = (p == 0) & dp2[i - c[j]][j - 1][0];
                }
            }
            else if (s[i] == '_'){
                dp2[i][j][1] = 0;
                dp2[i][j][0] = dp2[i - 1][j][0] | dp2[i - 1][j][1];
            }
            else{
                if (j == 0 || i < c[j]) dp2[i][j][1] = 0;
                else{
                    int p = pre[i] - pre[i - c[j]];
                    dp2[i][j][1] = (p == 0) & dp2[i - c[j]][j - 1][0];
                }

                dp2[i][j][0] = dp2[i - 1][j][0] | dp2[i - 1][j][1];
            }

            //cout<<i<<sp<<j<<" : "<<dp2[i][j][0]<<sp<<dp2[i][j][1]<<endl;
        }
    }

    string ans;
    for (int i = 1; i <= k; i++){
        for (int j = 1; j <= n; j++){
            pre_one[i][j] = pre_one[i][j - 1];
            int curr = dp2[j - 1][i - 1][0] & dp[j][i][1];
            pre_one[i][j] += curr;
        }
    }
    for (int i = 1; i <= n; i++){
        int one = 0, zero = 0;
        for (int j = 1; j <= k; j++){
            /*
            for (int l = max((int)0, i - c[j] + 1); l <= i; l++){
                int curr = dp2[l - 1][j - 1][0] & dp[l][j][1];
                one |= curr;
            }*/
            int tmp = pre_one[j][i] - pre_one[j][max((int)0, i - c[j])];
            if (tmp > 0) one |= 1;
        }
        for (int j = 0; j <= k; j++){
            int curr = dp2[i][j][0] & (dp[i + 1][j + 1][0] | dp[i + 1][j + 1][1]);
            //cout<<i<<sp<<j<<sp<<curr<<endl;
            zero |= curr;
        }
        if (one && zero) ans.pb('?');
        else if (one) ans.pb('X');
        else ans.pb('_');
    }
    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