Submission #352339

#	Time	Username	Problem	Language	Result	Execution time	Memory
352339		EndRay	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	492 KiB

paint

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

using namespace std;

const int N = 2e5+2, logN = 18+1, K = 100+2;

string s;
int n, k;
bool dp[N][K], rdp[N][K];
bool can_black[N];

int fl[N];
bool table[logN][N];

void init(){
    fl[1] = 0;
    for(int i = 2; i < n; ++i)
        fl[i] = fl[i/2]+1;
    for(int i = 1; i < n; ++i)
        table[0][i] = (s[i] != '_');
    for(int d = 0; d < logN-1; ++d)
        for(int i = 1; i < n-(1<<(d+1))+1; ++i)
            table[d+1][i] = table[d][i] | table[d][i+(1<<d)];
}

int get(int l, int r){ /// [l, r)
    int level = fl[r-l];
    return table[level][l] | table[level][r-(1<<level)];
}

string solve_puzzle(string s, vector<int> c) {
    s = "#" + s;
    ::s = s;
    c.insert(c.begin(), -1);
    n = s.size();
    k = c.size();
    s = s + "#";
    init();
    dp[0][0] = true;
    for(int i = 1; i < n; ++i){
        dp[i][0] = (s[i] != 'X' && dp[i-1][0]);
        for(int j = 1; j < k; ++j)
            dp[i][j] |= (s[i] != '_' && i >= c[j] && (i == c[j] && j == 1 || i != c[j] && s[i-c[j]] != 'X' && dp[i-c[j]-1][j-1]) && get(i-c[j]+1, i+1)) || (s[i] != 'X' && dp[i-1][j]);
    }
    rdp[n][k] = true;
    for(int i = n-1; i >= 1; --i){
        rdp[i][k] = (s[i] != 'X' && rdp[i+1][k]);
        for(int j = k-1; j >= 1; --j)
            rdp[i][j] |= (s[i] != '_' && i <= n-c[j] && (i == n-c[j] && j == k-1 || i != n-c[j] && s[i+c[j]] != 'X' && rdp[i+c[j]+1][j+1]) && get(i, i+c[j])) || (s[i] != 'X' && rdp[i+1][j]);
    }
    for(int j = 1; j < k; ++j){
        int rest = 0;
        if(j == 1){
            int i = 1;
            if(get(i, i+c[j]) && s[i+c[j]] != 'X' && rdp[i+c[j]+1][j+1])
                rest = c[j];
            if(rest) can_black[i] = rest--;
        }
        for(int i = 2; i < n-c[j]; ++i){
            if(get(i, i+c[j]) && s[i-1] != 'X' && s[i+c[j]] != 'X' && dp[i-2][j-1] && rdp[i+c[j]+1][j+1])
                rest = c[j];
            if(rest) can_black[i] = rest--;
        }
        if(j == k-1){
            int i = n-c[j];
            if(get(i, i+c[j]) && s[i-1] != 'X' && dp[i-2][j-1])
                rest = c[j];
        }
        for(int i = n-c[j]; i < n; ++i)
            if(rest) can_black[i] = rest--;
    }
    string ans = s;
    for(int i = 1; i < n; ++i){
        if(ans[i] == '.'){
            bool can_white = false;
            for(int j = 0; j < k; ++j)
                if(dp[i-1][j] && rdp[i+1][j+1]){
                    can_white = true;
                    break;
                }
            if(!can_white) ans[i] = 'X';
            else if(!can_black[i]) ans[i] = '_';
            else ans[i] = '?';
        }
    }
    return ans.substr(1, n-1);
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:44:65: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   44 |             dp[i][j] |= (s[i] != '_' && i >= c[j] && (i == c[j] && j == 1 || i != c[j] && s[i-c[j]] != 'X' && dp[i-c[j]-1][j-1]) && get(i-c[j]+1, i+1)) || (s[i] != 'X' && dp[i-1][j]);
      |                                                       ~~~~~~~~~~^~~~~~~~~
paint.cpp:50:70: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   50 |             rdp[i][j] |= (s[i] != '_' && i <= n-c[j] && (i == n-c[j] && j == k-1 || i != n-c[j] && s[i+c[j]] != 'X' && rdp[i+c[j]+1][j+1]) && get(i, i+c[j])) || (s[i] != 'X' && rdp[i+1][j]);
      |                                                          ~~~~~~~~~~~~^~~~~~~~~~~

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