제출 #205435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
205435		oko	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2087 ms	263604 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
#include <vector>
#include <string>
#include <cstdio>
#include <cassert>
using namespace std;
string a;
vector<int>k;
int dp[200005][105][3],wt[200005],bk[200005],ps[200005],of[200005],sum;
int f(int x,int y,int cl)
{
    if(x==a.size()-1)
    {
        if(y==k.size())return 1;
        else return 0;
    }
    if(dp[x][y][cl]!=-1)return dp[x][y][cl];
    int ans=0,cnt=0;
    if(cl==0)
    {
        if(a[x+1]=='X'&&y!=k.size())ans=max(ans,f(x+1,y,1));
        if(a[x+1]=='_')ans=max(ans,f(x+1,y,0));
        if(a[x+1]=='.')
        {
            if(y!=k.size())ans=max(ans,f(x+1,y,1));
            ans=max(ans,f(x+1,y,0));
        }
        return dp[x][y][cl]=ans;
    }
    int i=x+k[y]-1;
    cnt=ps[i]-ps[x-1];
    if(cnt==k[y]&&a[i+1]!='X')ans=max(ans,f(i+1,y+1,0));
    return dp[x][y][cl]=ans;
}
string solve_puzzle(string s,vector<int> c)
{
    memset(dp,-1,sizeof dp);
    a=s,k=c;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]!='_')ps[i]++;
        ps[i]+=ps[i-1];
    }
    a.push_back('_');
    if(a[0]!='X')f(0,0,0);
    if(a[0]!='_')f(0,0,1);
    for(int i=0; i<a.size(); i++)
    {
        for(int j=0; j<=k.size(); j++)
        {
            if(dp[i][j][1]==1)
            {
                int z=i+k[j]-1;
                if(ps[z]-ps[i-1]==k[j])
                {
                    sum++;
                    of[z+1]--;
                }
            }
            if(dp[i][j][0]==1)wt[i]=1;
        }
        sum+=of[i];
        if(sum)bk[i]=1;
    }
    string aa=a;
    for(int i=0;i<a.size();i++)
    {
        if(aa[i]!='.')continue;
        if(wt[i]+bk[i]==2)
        {
            aa[i]='?';
            continue;
        }
        if(wt[i])aa[i]='_';
        else aa[i]='X';
    }
    aa.erase(--aa.end());
    return aa;
}

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

paint.cpp: In function 'int f(int, int, int)':
paint.cpp:13:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(x==a.size()-1)
        ~^~~~~~~~~~~~
paint.cpp:15:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(y==k.size())return 1;
            ~^~~~~~~~~~
paint.cpp:22:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(a[x+1]=='X'&&y!=k.size())ans=max(ans,f(x+1,y,1));
                         ~^~~~~~~~~~
paint.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(y!=k.size())ans=max(ans,f(x+1,y,1));
                ~^~~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a.size();i++)
                 ~^~~~~~~~~
paint.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++)
                  ~^~~~~~~~~
paint.cpp:50:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<=k.size(); j++)
                      ~^~~~~~~~~~
paint.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a.size();i++)
                 ~^~~~~~~~~

• 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