Submission #823297

#	Time	Username	Problem	Language	Result	Execution time	Memory
823297		Alihan_8	Paint By Numbers (IOI16_paint)	C++17	80 / 100	4 ms	340 KiB

paint

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
//#define int long long

template <class _T>
bool chmin(_T &x, const _T &y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}

template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag = false;
    if ( x < y ){
        x = y; flag |= true;
    }
    return flag;
}

string solve_puzzle(string s, vector<int> c) {
    int n = (int)s.size(), m = (int)c.size();
    if ( n <= 100 ){
        auto ok = [&](string s){
            vector <vector<int>> dp(n + 1, vector <int> (m + 1));
            dp[0][0] = true;
            vector <int> pf(n + 1);
            for ( int i = 0; i < n; i++ ){
                pf[i + 1] = pf[i] + (s[i] == '_');
            }
            auto get = [&](int l, int r){
                return pf[r] - pf[l - 1];
            };
            s = '#' + s;
            for ( int i = 1; i <= n; i++ ){
                for ( int j = 0; j <= m; j++ ){
                    if ( s[i] != 'X' ){
                        dp[i][j] |= dp[i - 1][j];
                    }
                    if ( !j ) continue;
                    int k = i - c[j - 1];
                    if ( k >= 0 && !get(k + 1, i) ){
                        if ( !k and j <= 1 ){
                            dp[i][j] = true;
                        } else if ( k and s[k] != 'X' ){
                            dp[i][j] |= dp[k - 1][j - 1];
                        }
                    }
                }
            }
            return dp[n][m];
        };
        string ans = s;
        for ( int i = 0; i < n; i++ ){
            if ( s[i] != '.' ){
                continue;
            }
            for ( auto j: {'_', 'X'} ){
                s[i] = j;
                if ( ok(s) ){
                    if ( ans[i] != '.' ){
                        ans[i] = '?';
                    } else ans[i] = j;
                }
            }
            s[i] = '.';
        }
        return ans;
    }
    bool dp[n + 2][m + 1], dp2[n + 2][m + 1];
    for ( int i = 0; i <= n + 1; i++ ){
        for ( int j = 0; j <= m; j++ ){
            dp[i][j] = dp2[i][j] = false;
        }
    }
    vector <int> pf(n + 1);
    for ( int i = 0; i < n; i++ ){
        pf[i + 1] = pf[i] + (s[i] == '_');
    }
    auto get = [&](int l, int r){
        return pf[r] - pf[l - 1];
    };
    s = '#' + s + '#';
    dp[0][0] = true;
    for ( int i = 1; i <= n; i++ ){
        dp[i][0] = true;
        for ( int j = 1; j <= m; j++ ){
            if ( s[j] != 'X' ){
                dp[i][j] |= dp[i - 1][j];
            }
            int k = i - c[j - 1];
            if ( k >= 0 and !get(k + 1, i) ){
                if ( s[k] == 'X' ){
                    continue;
                }
                dp[i][j] |= dp[max(0, k - 1)][j - 1];
            }
        }
    }
    dp2[n + 1][0] = true;
    for ( int i = n; i > 0; i-- ){
        dp2[i][0] = true;
        for ( int j = 1; j <= m; j++ ){
            if ( s[j] != 'X' ){
                dp2[i][j] |= dp2[i + 1][j];
            }
            int k = i + c[m - j];
            if ( k <= n + 1 and !get(i, k - 1) ){
                if ( s[k] == 'X' ){
                    continue;
                }
                dp2[i][j] |= dp2[min(n + 1, k + 1)][j - 1];
            }
        }
    }
    vector <int> w(n + 2), b(n + 2);
    for ( int i = 1; i <= n; i++ ){
        if ( s[i] == 'X' ){
            continue;
        }
        for ( int j = 0; j <= m; j++ ){
            if ( dp[i - 1][j] && dp2[i + 1][m - j] ){
                w[i] = true;
            }
        }
    }
    for ( int j = 1; j <= m; j++ ){
        int t = c[j - 1];
        for ( int i = 1; i + t <= n + 1; i++ ){
            if ( get(i, i + t - 1) ){
                continue;
            }
            if ( s[i - 1] == 'X' or s[i + t] == 'X' ){
                continue;
            }
            if ( dp[max(0, i - 2)][j - 1] & dp2[min(n + 1, i + t + 1)][m - j] ){
                b[i]++; b[i + t]--;
            }
        }
    }
    for ( int i = 1; i <= n; i++ ){
        b[i] += b[i - 1];
    }
    string ans;
    for ( int i = 1; i <= n; i++ ){
        if ( b[i] && w[i] ){
            ans += '?';
        } else if ( b[i] ){
            ans += 'X';
        } else ans += '_';
    }
    return ans;
}

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