제출 #57073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57073		alenam0161	Paint By Numbers (IOI16_paint)	C++17	90 / 100	15 ms	4316 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
const int N = 100007;
const int K = 107;
bool suf[N][K];
bool pre[N][K];
int gum[N];
int vl[N];
int g[N];
std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n=s.length();
    int k=c.size();
    for(int i=0;i<n;++i){
        if(i)gum[i]+=gum[i-1];
        gum[i]+=(s[i]=='_');
    }
    auto sum=[&](int l,int r){
        return gum[r]-(l==0 ? 0:gum[l-1]);
    };
    suf[n][k]=true;
    suf[n+1][k]=true;
    for(int i=n-1;i>=0;i--){
        for(int j=k;j>=0;--j){
            if(s[i]!='X'&&suf[i+1][j])suf[i][j]=true;
            if(j==k)continue;
            if(c[j]+i-1<n&&sum(i,i+c[j]-1)==0){
                if(i+c[j]<n&&s[i+c[j]]=='X')continue;
                if(suf[i+c[j]+1][j+1]==false)continue;
                suf[i][j]=true;
            }
        }
    }
    for(int i=0;i<n;++i){
        for(int j=-1;j<k;++j){
            int z=(i==0&&j==-1);
            if(s[i]!='X'&&z)pre[0][0]=true;
            if(s[i]!='X'&&z==false&&pre[i-1][j+1]==true)pre[i][j+1]=true;
            if(j==-1)continue;
            if(i-c[j]+1>=0&&sum(i-c[j]+1,i)==0){
                if(i-c[j]>=0&&s[i-c[j]]=='X')continue;
                if(i-c[j]-1<0&&j!=0)continue;
                if(i-c[j]-1>=0&&pre[i-c[j]-1][j]==false)continue;
                pre[i][j+1]=true;
            }
        }
    }
    for(int i=0;i<n;++i){
        for(int j=-1;j<k;++j){
            if(s[i]!='.')continue;
            bool okl=false;
            bool okr=false;
            if(suf[i+1][j+1]==true)okr=true;
            okl=(i==0&&j==-1)||(!(i==0&&j==-1)&&pre[i-1][j+1]);
            if(okr&&okl)vl[i]|=1;
        }
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<k;++j){
            if(s[i]=='_')continue;
            bool ok=false;
            if(c[j]+i-1<n){
                bool x=true;
                if(i>0){
                    if(s[i-1]=='X')x=false;
                    else if(i-2>=0){
                    if(pre[i-2][j]==false){
                        x=false;
                    }
                    }
                    else if(j!=0)x=false;
                }
                else if(j!=0)x=false;
                if(x==false)continue;
                if(c[j]+i==n){
                    if(pre[c[j]+i-1][j+1]==true&&j==k-1&&sum(i,c[j]+i-1)==0)
                        g[i]=max(g[i],c[j]);
                }
                else
                if(pre[c[j]+i-1][j+1]==true&&suf[c[j]+i+1][j+1]==true&&s[c[j]+i]!='X'&&sum(i,c[j]+i-1)==0){
                    g[i]=max(g[i],c[j]);
                }
            }
        }
    }

    for(int i=0;i<n;++i){
        if(g[i]>0)vl[i]|=2;
        g[i+1]=max(g[i+1],g[i]-1);
    }
    for(int i=0;i<n;++i){
        if(s[i]=='.'){
            if(vl[i]==0)assert(0);
            if(vl[i]==1)s[i]='_';
            if(vl[i]==2)s[i]='X';
            if(vl[i]==3)s[i]='?';
        }
    }
    return s;
}

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:62:18: warning: unused variable 'ok' [-Wunused-variable]
             bool ok=false;
                  ^~

• 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: 0 / 10