Submission #773514

#	Time	Username	Problem	Language	Result	Execution time	Memory
773514		Amylopectin	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	212 KiB

paint

#include "paint.h"
#include <string>
#include <cstdlib>
using namespace std;
const int mxn = 210;
int m,c[mxn] = {},dp[mxn][mxn] = {},ru,fr[mxn],to[mxn] = {};
string ans;
string cal(int cl,int cr,int len)
{
    int i,j,cn,cm,fn,fm,su = -1,accu = -1;
    string s;
    if(cl > cr)
    {
        for(i=0; i<len; i++)
        {
            s.push_back('_');
        }
        return s;
    }
    for(i=0; i<len; i++)
    {
        s.push_back('?');
    }
    for(i=cl; i<=cr; i++)
    {
        su += c[i]+1;
    }
    for(j=cl; j<=cr; j++)
    {
        for(i=len-su+accu+1; i<accu+c[j]+1; i++)
        {
            s[i] = 'X';
        }
        accu += c[j]+1;
    }
    if(su == len)
    {
        for(i=0; i<len; i++)
        {
            if(s[i] == '?')
            {
                s[i] = '_';
            }
        }
    }
    return s;
}
int re(int ch,int ccn)
{
    if(dp[ch][ccn] != -1)
    {
        return dp[ch][ccn];
    }
    // if(ch == ru)
    // {
    //     if(ru == )
    // }
    int i,j,cm,fn,fm,ret,su = -1,clen = to[ch] - fr[ch]+1,of = 0;
    string s;
    for(i=ccn-1; i<m; i++)
    {
        if(su > clen)
        {
            break;
        }
        ret = re(ch+1,i+1);
        if(ret == 1)
        {
            of = 1;
            s = cal(ccn,i,clen);
            for(j=0; j<clen; j++)
            {
                cm = fr[ch] + j;
                if(ans[cm] == '0')
                {
                    ans[cm] = s[j];
                }
                else if(s[j] == '?')
                {
                    ans[cm] = '?';
                }
                else if((s[j] == '_' && ans[cm] == 'X') || (s[j] == 'X' && ans[cm] == '_'))
                {
                    ans[cm] = '?';
                }
            }
        }
        su += c[i+1] + 1;
    }
    dp[ch][ccn] = of;
    return of;
}
std::string solve_puzzle(std::string s, std::vector<int> cc) 
{
    int i,j,n,be;
    string fa;
    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<ru; i++)
    {
        for(j=0; j<=m; j++)
        {
            dp[i][j] = -1;
        }
    }
    for(j=0; j<m; j++)
    {
        dp[ru][j] = 0;
    }
    dp[ru][m] = 1;
    re(0,0);
    // ans = cal(0,m-1,n);

    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string cal(int, int, int)':
paint.cpp:10:13: warning: unused variable 'cn' [-Wunused-variable]
   10 |     int i,j,cn,cm,fn,fm,su = -1,accu = -1;
      |             ^~
paint.cpp:10:16: warning: unused variable 'cm' [-Wunused-variable]
   10 |     int i,j,cn,cm,fn,fm,su = -1,accu = -1;
      |                ^~
paint.cpp:10:19: warning: unused variable 'fn' [-Wunused-variable]
   10 |     int i,j,cn,cm,fn,fm,su = -1,accu = -1;
      |                   ^~
paint.cpp:10:22: warning: unused variable 'fm' [-Wunused-variable]
   10 |     int i,j,cn,cm,fn,fm,su = -1,accu = -1;
      |                      ^~
paint.cpp: In function 'int re(int, int)':
paint.cpp:58:16: warning: unused variable 'fn' [-Wunused-variable]
   58 |     int i,j,cm,fn,fm,ret,su = -1,clen = to[ch] - fr[ch]+1,of = 0;
      |                ^~
paint.cpp:58:19: warning: unused variable 'fm' [-Wunused-variable]
   58 |     int i,j,cm,fn,fm,ret,su = -1,clen = to[ch] - fr[ch]+1,of = 0;
      |                   ^~

• 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