Submission #774003

#	Time	Username	Problem	Language	Result	Execution time	Memory
774003		Amylopectin	Paint By Numbers (IOI16_paint)	C++14	80 / 100	8 ms	8916 KiB

paint

#include "paint.h"
#include <string>
#include <cstdlib>
using namespace std;
const int mxn = 210;
int m,n,c[mxn] = {},dp[mxn][mxn][mxn][2] = {},ru,fr[mxn],to[mxn] = {};
string ans,pate;
int ad(int cn,string cad)
{
    if(ans[cn] != '?')
    {
        if(ans[cn] == '0')
        {
            ans[cn] = cad[0];
        }
        else if(ans[cn] != cad[0])
        {
            ans[cn] = '?';
        }
    }
    return 0;
}
int re(int cn,int ch,int cbl,int tog)
{
    if(cn == n && ch== m && cbl == 0)
    {
        return 1;
    }
    if(cn >= n)
    {
        return 0;
    }
    if(dp[cn][ch][cbl][tog] != -1)
    {
        return dp[cn][ch][cbl][tog];
    }
    int i,j,cm,fn,fm,of = 0,ret;
    if(cbl == 0 && pate[cn] != 'X')
    {
        ret = re(cn+1,ch,cbl,0);
        of |= ret;
        if(ret == 1)
        {
            ad(cn,"_");
        }
    }
    if(pate[cn] != '_' && pate[cn+1] != 'X')
    {
        if(cbl+1 == c[ch] && tog == 0)
        {
            ret = re(cn+1,ch+1,0,1);
            of |= ret;
            if(ret == 1)
            {
                ad(cn,"X");
            }
        }
    }
    if(pate[cn] != '_' && ch < m && cbl < c[ch]-1 && tog == 0)
    {
        
        // else 
        {
            ret = re(cn+1,ch,cbl+1,0);
            of |= ret;
            if(ret == 1)
            {
                ad(cn,"X");
            }
        }
    }
    // if(of == 1)
    // {
    //     if(cbl == 0)
    //     {
    //         ad(cn,"_");
    //     }
    //     else 
    //     {
    //         ad(cn,"X");
    //     }
    // }
    dp[cn][ch][cbl][tog] = of;
    return of;
}
std::string solve_puzzle(std::string s, std::vector<int> cc) 
{
    int i,j,k,be;
    string fa;
    pate = s;
    n = s.size();
    m = cc.size();
    for(i=0; i<m; i++)
    {
        c[i] = cc[i];
    }
    ru = 0;
    be = 0;
    for(i=0; i<n; i++)
    {
        ans.push_back('0');
    }
    // for(i=0; i<n-1; i++)
    // {
    //     if(s[i] == '_')
    //     {
    //         ans[i] = '_';
    //     }
    //     if(s[i]!= s[i+1])
    //     {
    //         if(s[i] == '.')
    //         {
    //             fr[ru] = be;
    //             to[ru] = i;
    //             ru++;
    //         }
    //         else 
    //         {
    //             be = i+1;
    //         }
    //     }
    // }
    // if(s[n-1] == '_')
    // {
    //     ans[n-1] = '_';
    // }
    // if(s[n-1] == '.')
    // {
    //     fr[ru] = be;
    //     to[ru] = n-1;
    //     ru++;
    // }

    for(i=0; i<n; i++)
    {
        for(j=0; j<=m; j++)
        {
            for(k=0; k<=c[j]; k++)
            {
                dp[i][j][k][0] = -1;
                dp[i][j][k][1] = -1;
            }
        }
    }
    // for(j=0; j<n; j++)
    // {
    //     dp[ru][j] = 0;
    // }
    dp[n][m][0][0] = 1;
    dp[n][m][0][1] = 1;
    re(0,0,0,0);
    // if(s[0] == '_' || s[0] == '.')
    // {
    //     // re(0,0,0);
    // }
    // if(s[0] == 'X' || s[0] == '.')
    // {
    //     re(0,0,1);
    // }
    // ans = cal(0,m-1,n);

    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'int re(int, int, int, int)':
paint.cpp:37:9: warning: unused variable 'i' [-Wunused-variable]
   37 |     int i,j,cm,fn,fm,of = 0,ret;
      |         ^
paint.cpp:37:11: warning: unused variable 'j' [-Wunused-variable]
   37 |     int i,j,cm,fn,fm,of = 0,ret;
      |           ^
paint.cpp:37:13: warning: unused variable 'cm' [-Wunused-variable]
   37 |     int i,j,cm,fn,fm,of = 0,ret;
      |             ^~
paint.cpp:37:16: warning: unused variable 'fn' [-Wunused-variable]
   37 |     int i,j,cm,fn,fm,of = 0,ret;
      |                ^~
paint.cpp:37:19: warning: unused variable 'fm' [-Wunused-variable]
   37 |     int i,j,cm,fn,fm,of = 0,ret;
      |                   ^~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:88:15: warning: variable 'be' set but not used [-Wunused-but-set-variable]
   88 |     int i,j,k,be;
      |               ^~

• 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