제출 #479485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
479485		ponytail	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	332 KiB

paint

#include "paint.h"

#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <bits/stdc++.h>

using namespace std;

std::string solve_puzzle(std::string s, std::vector<int> c) {
    int k = c.size();
    int n = s.size();
    int ps[2][n]; // X _
    ps[0][0] = (s[0] == 'X');
    ps[1][0] = (s[0] == '_');
    for(int i=1; i<n; i++) {
        ps[0][i] = ps[0][i-1] + (s[i] == 'X');
        ps[1][i] = ps[1][i-1] + (s[i] == '_');
    }
    int can[2][n]; // X _
    for(int i=0; i<2; i++) {
        for(int j=0; j<n; j++) {
            can[i][j] = 0;
        }
    }
    int mx[n];
    int prv = 0;
    for(int i=0; i<n; i++) {
        if(s[i] == 'X') prv = i;
        mx[i] = prv;
    }
    int mx2[n];
    prv = n-1;
    for(int i=n-1; i>=0; i--) {
        if(s[i] == 'X') prv = i;
        mx2[i] = prv;
    }
    if(k == 1) {
        int ok[n] = {};
        for(int i=c[0]-1; i<n; i++) {
            if(ps[1][i] - (i == c[0] - 1 ? 0 : ps[1][i - c[0]]) == 0) {
                if(i == c[0] - 1 || ps[0][i - c[0]] == 0) {
                    if(ps[0][n-1] - ps[0][i] == 0) {
                        ok[i] = 1;
                    }
                }
            }
        }
        for(int i=1; i<n; i++) ok[i] += ok[i-1];
        for(int i=0; i<n; i++) {
            can[0][i] = ok[min(n-1, i + c[0] - 1)] - (i > 0 ? ok[i-1] : 0);
            can[1][i] = (i > 0 && ok[i-1] > 0 && ps[0][n-1] - ps[0][i] == 0) || (s[i] != 'X' && i + c[0] < n && ok[min(n - 1, mx2[i] + c[0] - 1)] - ok[i + c[0] - 1] > 0 && (i == 0 ? 0 : ps[0][i-1]) == 0);
        }
    }
    else {
        bool dp_forward[k][n];
        bool dp_backward[k][n];
        for(int i=0; i<k; i++) {
            for(int j=0; j<n; j++) {
                dp_forward[i][j] = dp_backward[i][j] = 0;
            }
        }

        int dp_forsum[k][n];
        int dp_backsum[k][n];
        for(int i=0; i<k; i++) {
            for(int j=0; j<n; j++) {
                dp_forsum[i][j] = dp_backsum[i][j] = 0;
            }
        }

        int real_dp[k][n]; // The real answer to question "i-th black segment ENDING at j-th column?"
        int real_sum[k][n];
        for(int i=0; i<k; i++) {
            for(int j=0; j<n; j++) {
                real_dp[i][j] = 0;
                real_sum[i][j] = 0;
            }
        }

        for(int i=c[0]-1; i<n; i++) {
            if(ps[1][i] - (i == c[0] - 1 ? 0 : ps[1][i - c[0]]) == 0) {
                if(i == c[0] - 1 || ps[0][i - c[0]] == 0) {
                    dp_forward[0][i] = 1;
                }
            }
            dp_forsum[0][i] = (i == 0 ? 0 : dp_forsum[0][i-1]) + dp_forward[0][i];
        }
        int cum = c[0] + 1;
        for(int i=1; i<k; i++) {
            cum += c[i];
            for(int j=cum-1; j<n; j++) {
                if(ps[1][j] - ps[1][j-c[i]] > 0) {
                    dp_forsum[i][j] = dp_forsum[i][j-1] + dp_forward[i][j];
                    continue;
                }
                if(s[j - c[i]] == 'X') {
                    dp_forsum[i][j] = dp_forsum[i][j-1] + dp_forward[i][j];
                    continue;
                }
                dp_forward[i][j] = (dp_forsum[i-1][j-c[i]-1] - (mx[j-c[i]] == 0 ? 0 : dp_forsum[i-1][mx[j-c[i]]-1]) > 0);
                dp_forsum[i][j] = dp_forsum[i][j-1] + dp_forward[i][j];
            }
            cum++;
        }

        for(int i=0; i<n - c[k-1] + 1; i++) {
            if(ps[1][i + c[k-1] - 1] - (i > 0 ? ps[1][i-1] : 0) == 0) {
                if(ps[0][n-1] - ps[0][i + c[k-1] - 1] == 0) {
                    if(i == 0 || ps[0][i-1] == 0) {
                        dp_backward[k-1][i] = 1;
                    }
                }
            }
            dp_backsum[k-1][i] = (i == 0 ? 0 : dp_backsum[k-1][i-1]) + dp_backward[k-1][i];
        }
        for(int i=n-c[k-1]+1; i<n; i++) {
            dp_backsum[k-1][i] = (i == 0 ? 0 : dp_backsum[k-1][i-1]) + dp_backward[k-1][i];
        }
        cum = c[k-1] + 1;
        for(int i=k-2; i>=0; i--) {
            cum += c[i] - 1;
            for(int j=0; j<n-cum; j++) {
                if(ps[1][j + c[i] - 1]-(j > 0 ? ps[1][j-1] : 0) > 0) {
                    dp_backsum[i][j] = (j==0 ? 0 : dp_backsum[i][j-1]) + dp_backward[i][j];
                    continue;
                }
                if(s[j + c[i]] == 'X') {
                    dp_backsum[i][j] = (j==0 ? 0 : dp_backsum[i][j-1]) + dp_backward[i][j];
                    continue;
                }
                dp_backward[i][j] = (dp_backsum[i+1][mx2[j + c[i]]] - dp_backsum[i+1][j+c[i]] > 0);
                dp_backsum[i][j] = (j==0 ? 0 : dp_backsum[i][j-1]) + dp_backward[i][j];
            }
            for(int j=n-cum; j<n; j++) {
                dp_backsum[i][j] = (j==0 ? 0 : dp_backsum[i][j-1]) + dp_backward[i][j];
            }
            cum += 2;
        }

        for(int i=0; i<k; i++) {
            for(int j=0; j<n; j++) {
                if(j+1<n && s[j+1] == 'X') {
                    real_sum[i][j] = (j == 0 ? 0 : real_sum[i][j-1]) + real_dp[i][j];
                    continue;
                }
                if(j == n-1) {
                    if(i == k-1) real_dp[i][j] = dp_forward[i][j];
                    real_sum[i][j] = (j == 0 ? 0 : real_sum[i][j-1]) + real_dp[i][j];
                    continue;
                }
                if(i == k-1) {
                    real_dp[i][j] = dp_forward[i][j] && (ps[0][n-1] - ps[0][j] == 0);
                    real_sum[i][j] = (j == 0 ? 0 : real_sum[i][j-1]) + real_dp[i][j];
                    continue;
                }
                real_dp[i][j] = dp_forward[i][j] && (dp_backsum[i+1][mx2[j+1]] - dp_backsum[i+1][j+1] > 0);
                real_sum[i][j] = (j == 0 ? 0 : real_sum[i][j-1]) + real_dp[i][j];
                if(real_dp[i][j]) assert(s[j] != '_');
            }
        }
        for(int i=0; i<n; i++) {
            for(int j=0; j<k; j++) {
                if(real_sum[j][min(n-1, i+c[j]-1)] - (i==0 ? 0 : real_sum[j][i-1]) > 0) {
                    can[0][i] = 1;
                }
            }
            for(int j=0; j<k-1; j++) {
                if(s[i] != 'X' && i>0 && real_sum[j][i-1] && i + c[j+1] < n && (real_sum[j+1][n-1] - real_sum[j+1][i + c[j+1] - 1] > 0)) {
                    can[1][i] = 1;
                }
            }
            if(s[i] != 'X' && real_sum[0][min(n-1, mx2[i] + c[0] - 1)] - real_sum[0][min(n-1, i + c[0] - 1)] > 0) {
                can[1][i] = 1;
            }
            if(s[i] != 'X' && i > 0 && real_sum[k-1][i-1]) {
                can[1][i] = 1;
            }
        }
        
        for(int i=0; i<k; i++) {
            for(int j=0; j<n; j++) {
                if(real_dp[i][j]) assert(s[j] != '_');
            }
        }
        
    }
    string ans;
    for(int i=0; i<n; i++) {
        if(can[0][i] && can[1][i]) ans += "?";
        else if(can[0][i]) ans += "X";
        else ans += "_";
    }
    for(int i=0; i<n; i++) {
        //assert(!(s[i] == 'X' && ans[i] != 'X'));
        //assert(!(s[i] == '_' && ans[i] != '_'));
    }
    return ans;
}

• 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