Submission #70317

#	Time	Username	Problem	Language	Result	Execution time	Memory
70317		Eae02	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2059 ms	28956 KiB

paint

#include "paint.h"

#include <cstdlib>

struct Cell
{
    bool forcedW = false;
    bool forcedB = false;
    bool canW = false;
    bool canB = false;
};

std::vector<Cell> cells;

std::vector<int> blockSizes;

uint8_t memo[200000][100];

bool f(int i, int k)
{
    if (i >= cells.size())
        return k == blockSizes.size();
    if (memo[i][k] != 0)
        return memo[i][k] == 2;
    
    bool p = false;
    
    if (!cells[i].forcedB && f(i + 1, k))
    {
        cells[i].canW = true;
        p = true;
    }
    
    if (k < blockSizes.size() && i + blockSizes[k] <= cells.size())
    {
        int endIdx = i + blockSizes[k];
        bool placeWAtEnd = endIdx < cells.size();
        
        bool canB = true;
        
        if (placeWAtEnd && cells[endIdx].forcedB)
            canB = false;
        else
        {
            for (int j = 0; j < blockSizes[k]; j++)
            {
                if (cells[i + j].forcedW)
                {
                    canB = false;
                    break;
                }
            }
        }
        
        if (canB && f(i + blockSizes[k] + 1, k + 1))
        {
            for (int j = 0; j < blockSizes[k]; j++)
                cells[i + j].canB = true;
            
            if (placeWAtEnd)
                cells[i + blockSizes[k]].canW = true;
            
            p = true;
        }
    }
    
    memo[i][k] = p ? 2 : 1;
    return p;
}

std::string solve_puzzle(std::string s, std::vector<int> c)
{
    blockSizes = c;
    
    cells.resize(s.size());
    for (size_t i = 0; i < s.size(); i++)
    {
        cells[i].forcedB = s[i] == 'X';
        cells[i].forcedW = s[i] == '_';
    }
    
    f(0, 0);
    
    std::string ans(s.size(), '?');
    for (size_t i = 0; i < s.size(); i++)
    {
        if (cells[i].canB && !cells[i].canW)
            ans[i] = 'X';
        else if (!cells[i].canB && cells[i].canW)
            ans[i] = '_';
    }
    
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool f(int, int)':
paint.cpp:21:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i >= cells.size())
         ~~^~~~~~~~~~~~~~~
paint.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         return k == blockSizes.size();
                ~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:34:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (k < blockSizes.size() && i + blockSizes[k] <= cells.size())
         ~~^~~~~~~~~~~~~~~~~~~
paint.cpp:34:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (k < blockSizes.size() && i + blockSizes[k] <= cells.size())
                                  ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
paint.cpp:37:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         bool placeWAtEnd = endIdx < cells.size();
                            ~~~~~~~^~~~~~~~~~~~~~

• 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