제출 #773440

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

paint

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

int n,m,bef[200001],aft[200001],mark[200001],qs[200001],rqs[200001];
bool dp1[200001][101],dp2[200001][101];
bool canX[200001],canY[200001];
string ans;

string solve_puzzle(string s, vector<int> c) {
    n=s.size();
    m=c.size();
    int before=-1,after=n;

    for (int i=0; i<n; ++i) {
        if (i) qs[i]+=qs[i-1];
        if (s[i]=='X') ++qs[i];
        if (s[i]=='_') before=i;
        bef[i]=before;
    }

    for (int i=n-1; i>=0; --i) {
        if (i!=n-1) rqs[i]+=rqs[i+1];
        if (s[i]=='X') ++rqs[i];
        if (s[i]=='_') after=i;
        aft[i]=after;
    }


    for (int i=0; i<n; ++i) {
        for (int j=0; j<m; ++j) {
            if (i && s[i]!='X') dp1[i][j]=dp1[i-1][j];
            if (i-bef[i]>=c[j]) {
                if (i-c[j]-1>=0 && dp1[i-c[j]-1][j-1]) dp1[i][j]=true;
                else if (j==0) {
                    if (i-c[j]>=0) {
                        if (qs[i-c[j]]==0) dp1[i][j]=true;
                    } else dp1[i][j]=true;
                }
            }
        }
    }

    for (int i=n-1; i>=0; --i) {
        for (int j=0; j<m; ++j) {
            if (i!=n-1 && s[i]!='X') dp2[i][j]=dp2[i+1][j];
            if (aft[i]-i>=c[j]) {
                if (i+c[j]+1<n && dp2[i+c[j]+1][j+1]) {
                    dp2[i][j]=true;
                    if (j==0 || (i>=2 && dp1[i-2][j-1])) ++mark[i], --mark[i+c[j]];
                } else if (j==m-1) {
                    if (i+c[j]<n) {
                        if (rqs[i+c[j]]==0) {
                            dp2[i][j]=true;
                            if (j==0 || (i>=2 && dp1[i-2][j-1])) ++mark[i], --mark[i+c[j]];
                        }
                    } else {
                        dp2[i][j]=true;
                        if (j==0 || (i>=2 && dp1[i-2][j-1])) ++mark[i], --mark[i+c[j]];
                    }
                }
            }
        }
    }

    for (int i=0; i<n; ++i) {
        mark[i]+=mark[i-1];
        if (mark[i]) canX[i]=true;
        
        if ((i>=1 && dp1[i-1][m-1]) || (i<=n-2 && dp2[i+1][0])) canY[i]=true;

        for (int j=0; j<m-1; ++j) {
            if (i!=0 && i!=n-1 && dp1[i-1][j] && dp2[i+1][j+1]) canY[i]=true;
        }
    }

    for (int i=0; i<n; ++i) {
        if (s[i]=='X' || s[i]=='_') ans+=s[i];
        else {
            if (canX[i] && canY[i]) ans+='?';
            else if (canX[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: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10