Submission #673759

#	Time	Username	Problem	Language	Result	Execution time	Memory
673759		tbzard	Paint By Numbers (IOI16_paint)	C++14	100 / 100	399 ms	42692 KiB

paint

#include <bits/stdc++.h>
using namespace std;
bool space[200001];
int add[200002];
bool dp[200001][101], dp2[200001][101];
int sum[200001];
string solve_puzzle(string s, vector<int> c){
    int n = s.length(), k = c.size();
    for(int i=1;i<=n;i++){
        if(s[i-1] == '.' || s[i-1] == 'X') sum[i]++;
        sum[i] += sum[i-1];
    }
    dp[0][0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            if(dp[i-1][j] && (s[i-1] == '_' || s[i-1] == '.')) dp[i][j] = 1;
            if(j == 0){
                if(j < k && i >= c[j] && sum[i]-sum[i-c[j]] == c[j] && dp[i-c[j]][j]){
                    dp[i][j+1] = 1;
                }
            }
            else{
                if(j < k && i >= c[j]+1 && sum[i]-sum[i-c[j]] == c[j] && (s[i-c[j]-1] == '_' || s[i-c[j]-1] == '.')){
                    dp[i][j+1] |= dp[i-c[j]-1][j];
                }
            }
        }
    }
    dp2[n][k] = 1;
    for(int i=n;i>=1;i--){
        for(int j=k;j>=0;j--){
            if(dp2[i][j]){
                if(dp[i-1][j] && (s[i-1] == '_' || s[i-1] == '.')){
                    dp2[i-1][j] = 1;
                    space[i] = 1;
                }
                if(j == 1){
                    if(j > 0 && i >= c[j-1] && sum[i]-sum[i-c[j-1]] == c[j-1] && dp[i-c[j-1]][j-1]){
                        add[i]++;
                        add[i-c[j-1]]--;
                        dp2[i-c[j-1]][j-1] = 1;
                    }
                }
                else{
                    if(j > 0 && i >= c[j-1]+1 && sum[i]-sum[i-c[j-1]] == c[j-1] && dp[i-c[j-1]-1][j-1] && (s[i-c[j-1]-1] == '_' || s[i-c[j-1]-1] == '.')){
                        add[i]++;
                        add[i-c[j-1]]--;
                        space[i-c[j-1]] = 1;
                        dp2[i-c[j-1]-1][j-1] = 1;
                    }
                }
            }
        }
    }
    string ans = "";
    for(int i=0;i<n;i++) ans += '?';
    for(int i=n;i>=1;i--){
        add[i] += add[i+1];
        if(add[i] && !space[i]) ans[i-1] = 'X';
        else if(!add[i] && space[i]) ans[i-1] = '_';
    }
    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