# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
70317 | Eae02 | Paint By Numbers (IOI16_paint) | C++14 | 2059 ms | 28956 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |