Submission #1021839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021839		vjudge1	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	4544 KiB

paint

#include <bits/stdc++.h>
#define ent '\n'

typedef long long ll;
using namespace std;
const int maxn = 2e5+12;

int suff[maxn][103];
int pref[maxn][103];
bool can[maxn];
int prefw[maxn];
int prefb[maxn];
int c[maxn];
int n, k;

string solve_puzzle(string s, vector<int> C){
    n = s.size(), k = C.size();
    for(int i=0;i<n;i++){
        prefw[i+1] = prefw[i] + (s[i] == '_');
        prefb[i+1] = prefb[i] + (s[i] == 'X');
        c[i+1] = C[i];
    }
    string ans = "";
    pref[0][0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            if(s[i-1] != 'X') pref[i][j] = pref[i-1][j];
            if(j > 1 && i > c[j] && pref[i-c[j]-1][j-1] && prefw[i] == prefw[i-c[j]]) {
                pref[i][j] = 1;
            }
            if(j == 1 && i >= c[j] && pref[i-c[j]][j-1] && prefw[i] == prefw[i-c[j]]){
                pref[i][j] = 1;
            }
        }
    }
    suff[n+1][k+1] = 1;
    for(int i=n;i;i--){
        for(int j=k+1;j>0;j--){
            if(s[i-1] != 'X') suff[i][j] = suff[i+1][j];
            if(j < k && n - i + 1 > c[j] && suff[i+c[j]+1][j+1] && prefw[i+c[j]-1] == prefw[i-1]){
                suff[i][j] = 1;
            }
            if(j == k && n - i + 1 >= c[j] && suff[i+c[j]][j+1] && prefw[i+c[j]-1] == prefw[i-1]){
                suff[i][j] = 1;
            }
        }
    }
    for(int j=1;j<=k;j++){
        for(int l=1;l+c[j]-1<=n;l++){
            int r = l + c[j] - 1;
            if(prefw[r] - prefw[l-1] == 0 && r + (j != k) <= n && l - 1 - (j != 1) >= 0 && pref[l - 1 - (j != 1)][j-1] && suff[r + 1 + (j != k)][j+1] && (l == 1 || l > 1 && s[l-2] != 'X') && (r == n || r < n && s[r] != 'X')){
                for(int i=l;i<=r;i++){
                    can[i] = 1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        bool ok = 0, fg = 0;
        for(int j=0;j<=k;j++){
            if(pref[i-1][j] && suff[i+1][j+1] && s[i-1] != 'X'){
                fg = 1;
            }
        }
        if(!fg){
            ans += 'X';
        }
        else if(!can[i]){
            ans += '_';
        }
        else{
            ans += '?';
        }
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:51:171: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   51 |             if(prefw[r] - prefw[l-1] == 0 && r + (j != k) <= n && l - 1 - (j != 1) >= 0 && pref[l - 1 - (j != 1)][j-1] && suff[r + 1 + (j != k)][j+1] && (l == 1 || l > 1 && s[l-2] != 'X') && (r == n || r < n && s[r] != 'X')){
      |                                                                                                                                                                     ~~~~~~^~~~~~~~~~~~~~~~
paint.cpp:51:209: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   51 |             if(prefw[r] - prefw[l-1] == 0 && r + (j != k) <= n && l - 1 - (j != 1) >= 0 && pref[l - 1 - (j != 1)][j-1] && suff[r + 1 + (j != k)][j+1] && (l == 1 || l > 1 && s[l-2] != 'X') && (r == n || r < n && s[r] != 'X')){
      |                                                                                                                                                                                                           ~~~~~~^~~~~~~~~~~~~~
paint.cpp:59:14: warning: unused variable 'ok' [-Wunused-variable]
   59 |         bool ok = 0, fg = 0;
      |              ^~

• 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