Submission #70322

#	Time	Username	Problem	Language	Result	Execution time	Memory
70322		Eae02	Paint By Numbers (IOI16_paint)	C++14	100 / 100	782 ms	39800 KiB

paint

#include "paint.h"

#include <cstdlib>

struct Cell
{
    bool forcedB = false;
    bool canW = false;
    int delB = 0;
};

std::vector<Cell> cells;

std::vector<int> blockSizes;

uint8_t memo[200000][100];

int numForcedWBefore[200000];

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
        {
            if (numForcedWBefore[endIdx - 1] > (i == 0 ? 0 : numForcedWBefore[i - 1]))
                canB = false;
        }
        
        if (canB && f(endIdx + 1, k + 1))
        {
            cells[i].delB++;
            
            if (placeWAtEnd)
            {
                cells[endIdx].delB--;
                cells[endIdx].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;
    
    int numForcedW = 0;
    cells.resize(s.size());
    for (size_t i = 0; i < s.size(); i++)
    {
        cells[i].forcedB = s[i] == 'X';
        
        if (s[i] == '_')
            numForcedW++;
        numForcedWBefore[i] = numForcedW;
    }
    
    f(0, 0);
    
    std::string ans(s.size(), '?');
    int d = 0;
    for (size_t i = 0; i < s.size(); i++)
    {
        d += cells[i].delB;
        
        bool canB = d > 0;
        if (canB && !cells[i].canW)
            ans[i] = 'X';
        else if (!canB && cells[i].canW)
            ans[i] = '_';
    }
    
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool f(int, int)':
paint.cpp:22:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i >= cells.size())
         ~~^~~~~~~~~~~~~~~
paint.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         return k == blockSizes.size();
                ~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:35:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (k < blockSizes.size() && i + blockSizes[k] <= cells.size())
         ~~^~~~~~~~~~~~~~~~~~~
paint.cpp:35:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (k < blockSizes.size() && i + blockSizes[k] <= cells.size())
                                  ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
paint.cpp:38: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: 10 / 10