Submission #1180200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180200		HappyCapybara	Paint By Numbers (IOI16_paint)	C++20	100 / 100	403 ms	44104 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;

int n;
vector<vector<bool>> st;

bool query(int l, int r){
    int lg = 31 - __builtin_clz(r-l+1);
    return st[l][lg] | st[r-(1<<lg)+1][lg];
}

string solve_puzzle(string s, vector<int> c){
    //cout << "a" << endl;
    int k = c.size();
    n = s.size();
    st.resize(n, vector<bool>(20, false));
    for (int j=0; j<20; j++){
        for (int i=0; i<n; i++){
            if (j == 0){
                if (s[i] == '_') st[i][j] = true;
                continue;
            }
            if (i+(1<<(j-1)) < n) st[i][j] = st[i][j-1] | st[i+(1<<j-1)][j-1];
        }
    }
    vector<vector<bool>> dpl(n+2, vector<bool>(k+1, false)), dpr(n+2, vector<bool>(k+1, false));
    //cout << "b" << endl;
    for (int j=0; j<=k; j++){
        for (int i=0; i<=n+1; i++){
            if (i <= 1){
                if (j == 0) dpr[i][j] = true;
                else dpr[i][j] = false;
                continue;
            }
            if (j == 0){
                if (s[i-2] != 'X') dpr[i][j] = dpr[i-1][j];
                continue;
            }
            if ((s[i-2] != 'X') && dpr[i-1][j]){
                dpr[i][j] = true;
                continue;
            }
            if ((s[i-2] != '_') && i-2-c[j-1]+1 >= 0 && !query(i-2-c[j-1]+1, i-2) && (i-2-c[j-1] == -1 || s[i-2-c[j-1]] != 'X') && dpr[i-c[j-1]-1][j-1]) dpr[i][j] = true;
        }
    }
    //cout << "c" << endl;
    vector<int> pos(n, -1);
    for (int j=k; j>=0; j--){
        for (int i=n+1; i>=0; i--){
            if (i >= n){
                if (j == k) dpl[i][j] = true;
                else dpl[i][j] = false;
                continue;
            }
            if (j == k){
                if (s[i] != 'X') dpl[i][j] = dpl[i+1][j];
                continue;
            }
            if ((s[i] != '_') && i+c[j]-1 < n && !query(i, i+c[j]-1) && (i+c[j] == n || s[i+c[j]] != 'X') && dpl[i+c[j]+1][j+1]){
                dpl[i][j] = true;
                if ((i == 0 && j == 0) || (s[i-1] != 'X' && ((i == 1 && j == 0) || dpr[i-2+2][j]))) pos[i] = max(pos[i], i+c[j]-1);
            }
            if ((s[i] != 'X' || s[i] == '.') && dpl[i+1][j]) dpl[i][j] = true;
        }
    }
    /*for (int i=0; i<=n+1; i++){
        for (int j=0; j<=k; j++) cout << dpr[i][j];
        cout << endl;
    }*/
    string res = s;
    for (int i=0; i<n; i++){
        if (s[i] == '.'){
            for (int j=0; j<=k; j++){
                if (dpl[i+1][j] && dpr[i-1+2][j]){
                    res[i] = '_';
                    break;
                }
            }
        }
    }
    //cout << res << endl;
    int cur = 0;
    for (int l=0; l<n; l++){
        int r = pos[l];
        for (int i=max(l, cur); i<=r; i++){
            if (s[i] == '.'){
                if (res[i] == '_' || res[i] == '?') res[i] = '?';
                else res[i] = 'X';
            }
        }
    }
    return res;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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