Submission #559462

#	Time	Username	Problem	Language	Result	Execution time	Memory
559462		MohamedFaresNebili	Paint By Numbers (IOI16_paint)	C++14	100 / 100	398 ms	160176 KiB

paint

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        int DP[200001][101][2], A[200001];

        string solve_puzzle(string S, vector<int> C) {
            int N = S.length(), K = C.size(); string res(N, '?');
            DP[0][0][0] = 1; int P = 0;
            for(int l = 1; l <= N; l++) {
                if(S[l - 1] == '_') {
                    P = l;
                    for(int i = 0; i <= K; i++)
                        DP[l][i][0] = DP[l - 1][i][0];
                    continue;
                }
                if(S[l - 1] == '.') {
                    for(int i = 0; i <= K; i++)
                        DP[l][i][0] = DP[l - 1][i][0];
                }

                for(int i = 1; i <= K; i++) {
                    if(C[i - 1] <= l && P <= l - C[i - 1] && S[l - C[i - 1] - 1] != 'X')
                        DP[l][i][0] |= DP[max(0, l - C[i - 1] - 1)][i - 1][0];
                }
            }
            P = N + 1;
            DP[N + 1][K + 1][1] = 1;
            for(int l = N; l >= 1; l--) {
                if(S[l - 1] == '_') {
                    P = l;
                    for(int i = 1; i <= K + 1; i++)
                        DP[l][i][1] = DP[l + 1][i][1];
                    continue;
                }
                if(S[l - 1] == '.') {
                    for(int i = 1; i <= K + 1; i++)
                        DP[l][i][1] = DP[l + 1][i][1];
                }

                for(int i = 1; i <= K; i++) {
                    if(C[i - 1] + l - 1 <= N && P > C[i - 1] + l - 1 && S[l + C[i - 1] - 1] != 'X') {
                        DP[l][i][1] |= DP[min(N + 1, l + C[i - 1] + 1)][i + 1][1];
                        int U = DP[min(N + 1, l + C[i - 1] + 1)][i + 1][1];
                        int V = DP[max(0, l - 2)][i - 1][0];
                        if(U && V && S[l - 2] != 'X')
                            A[l]++, A[l + C[i - 1]]--;
                    }
                }
            }
            for(int l = 1; l <= N; l++) {
                if(S[l - 1] == '_') continue;
                for(int i = 1; i <= K; i++) {
                    if(C[i - 1] + l - 1 <= N && P > C[i - 1] + l - 1 && S[l + C[i - 1] - 1] != 'X') {
                        int U = DP[min(N + 1, l + C[i - 1] + 1)][i + 1][1];
                        int V = DP[max(0, l - 2)][i - 1][0];
                        if(U && V && S[l - 2] != 'X')
                                A[l]++, A[l + C[i - 1]]--;
                    }
                }
            }
            for(int l = 1; l <= N; l++) {
                A[l] += A[l - 1];
                if(S[l - 1] != '.') res[l - 1] = S[l - 1];
                else {
                    if(!A[l]) res[l - 1] = '_';
                    else {
                        int ok = 0;
                        for(int i = 0; i <= K; i++)
                            ok |= DP[l - 1][i][0] & DP[l + 1][i + 1][1];
                        if(!ok) res[l - 1] = 'X';
                        else res[l - 1] = '?';
                    }
                }
            }
            return res;
        }

• 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