Submission #1118283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118283		NotLinux	Paint By Numbers (IOI16_paint)	C++17	100 / 100	203 ms	43156 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
string solve_puzzle(string s, vector<int> c) {
    int n = sz(s) , m = sz(c);

    int ans[2][n+1] = {0};
    memset(ans , 0 , sizeof(ans));

    int pre[n+1] = {0};
    pre[0] = 0;
    for(int i = 0;i<n;i++){
        pre[i+1] = pre[i] + (s[i] == '_');
    }
    auto getsum = [&](int ql , int qr){// 0 indexed
        return pre[qr+1] - pre[ql];
    };
    bool dp[n+1][m+1] , vis[n+1][m+1];
    memset(dp , 0 , sizeof(dp));
    memset(vis , 0 , sizeof(vis));
    vis[0][0] = 1;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<=m;j++){
            // alma 
            if(s[i] != 'X'){
                vis[i+1][j] |= vis[i][j];
            }
            // al 
            if(j < m and i + c[j] - 1 < n and getsum(i , i + c[j] - 1) == 0){
                if((i + c[j] - 1) == n-1){
                    vis[i + c[j]][j+1] |= vis[i][j];
                }
                else if((i + c[j] - 1) < n-1 and s[i + c[j]] != 'X'){
                    vis[i + c[j] + 1][j+1] |= vis[i][j];
                }
            }
            // cout << i << " " << j << " : " << vis[i][j] << endl;
        }
    }
    dp[n][m] = vis[n][m];
    for(int i = n-1;i>=0;i--){
        for(int j = 0;j<=m;j++){
            if(vis[i][j] == 0)continue;
            // alma 
            if(s[i] != 'X' and dp[i+1][j]){
                dp[i][j] = 1;
                ans[0][i] = 1;
                // cout << "flag 0 : " << i << " " << j << endl;
            }
            // al 
            if(j < m and i + c[j] - 1 < n and getsum(i , i + c[j] - 1) == 0){
                if((i + c[j] - 1) == n-1  and dp[i + c[j]][j+1]){
                    dp[i][j] = 1;
                    ans[1][i]++;
                    ans[1][i + c[j]]--;
                    // cout << "flag 1 : " << i << " " << j << endl;
                }
                else if((i + c[j] - 1) < n-1 and s[i + c[j]] != 'X' and dp[i + c[j] + 1][j+1]){
                    dp[i][j] = 1;
                    ans[1][i]++;
                    ans[1][i + c[j]]--;
                    ans[0][i + c[j]] = 1;
                    // cout << "flag 2  : " << i << " " << j << endl;
                }
            }
        }
    }
    for(int i = 1;i<n;i++){
        ans[1][i] += ans[1][i-1];
    }
    string ret = s;
    for(int i = 0;i<n;i++){
        if(s[i] != '.')ret[i] = s[i];
        else {
            if(ans[0][i] and ans[1][i])ret[i] = '?';
            if(!ans[0][i] and ans[1][i])ret[i] = 'X';
            if(ans[0][i] and !ans[1][i])ret[i] = '_';
        }
    }
    return ret;
}

• 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