제출 #773401

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

paint

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

int n,m,bef[200001],aft[200001],mark[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 (s[i]=='_') before=i;
        bef[i]=before;
    }

    for (int i=n-1; i>=0; --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) dp1[i][j]=dp1[i-1][j];
            if (i-bef[i]>=c[j] && (j==0 || (i-c[j]-1>=0 && dp1[i-c[j]-1][j-1]))) dp1[i][j]=true;
        }
    }


    for (int i=n-1; i>=0; --i) {
        for (int j=0; j<m; ++j) {
            if (i!=n-1) dp2[i][j]=dp2[i+1][j];

            if (aft[i]-i>=c[j] && (j==m-1 || (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]];
            }
        }
    }

    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