Submission #412790

#	Time	Username	Problem	Language	Result	Execution time	Memory
412790		sad	Paint By Numbers (IOI16_paint)	C++14	80 / 100	16 ms	460 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"
#include <cstdlib>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int n,m;string s;
vector<int>c;int w,o;
int dp[109][109];
int d(int x,int y)
{
    if(y>m)return 0;
    if(x>=n&&y==m)return 1;
    if(x>=n)return 0;
    int &u=dp[x][y];
    if(u!=-1)
        return u;
    u=0;
    if(s[x]=='X')
    {
        if(x+c[y]>n)
            return u=0;
        for(int i=x;i<x+c[y]; i++)
        {
            if(s[i]=='_')
                return u;
        }
        if(s[x+c[y]]=='X')
            return u;
        u=d(x+c[y]+1,y+1);
        return u;
    }
    if(s[x]=='_')
    {
        u=d(x+1,y);
        return u;
    }

    u=d(x+1,y);
    if(x+c[y]>n)
        return u;
    for(int i=x;i<x+c[y]; i++)
    {
        if(s[i]=='_')
            return u;
    }
    if(s[x+c[y]]=='X')
        return u;
    u=max(u,d(x+c[y]+1,y+1));
    return u;

}
string ss;
string solve_puzzle(string S, vector<int> C)
{
    for(int i=0;i<C.size();i++)c.pb(C[i]);
    s=S;
    n=s.size();m=c.size();s+='_';c.pb(0);
    for(int i=0; i<n; i++)
    {
        if(s[i]!='.')
        {
            ss+=s[i];
            continue;
        }
        memset(dp,-1,sizeof dp);
        s[i]='X';
        int x=d(0,0);
        memset(dp,-1,sizeof dp);
        s[i]='_';
        int y=d(0,0);
        if(x+y==2)
            ss+='?';
        else if(x)
            ss+='X';
        else
            ss+='_';
        s[i]='.';
    }
    return ss;
}/*
if(x==w)
    {
        if(o==0)
        {
            if(x+c[y]>n)
                return u;
            for(int i=x; i<x+c[y]; i++)
            {
                if(s[i]=='_')
                    return u;
            }
            if(c[x+c[y]]=='X')
                return u;
            u=max(u,d(x+c[y]+1,y+1));
            return u;
        }
        else
        {
            u=d(x+1,y);
            return u;
        }
    }*/

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0;i<C.size();i++)c.pb(C[i]);
      |                 ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10