Submission #592244

#	Time	Username	Problem	Language	Result	Execution time	Memory
592244		Elias	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1110 ms	50656 KiB

paint

#include <bits/stdc++.h>

using namespace std;

#include "paint.h"

int n, k;
vector<bool> hi;
vector<int> cl;

vector<vector<bool>> dp;
vector<vector<bool>> seT;
vector<int> wh, bl;
vector<int> numWhite;

bool checkWhite(int l, int r)
{
	int cnt = numWhite[r - 1];
	if (l)
		cnt -= numWhite[l - 1];
	return cnt;
}

bool DP(int i, int j)
{
	if (i <= 0)
		return j == 0;

	if (seT[i][j])
		return dp[i][j];

	bool b = false;

	if (j > 0)
	{
		int size = cl[j - 1];

		if (i >= size && (i == size || !hi[i - size - 1]) && !checkWhite(i - size, i))
		{
			if (DP(i - size - 1, j - 1))
			{
				b = true;
				if (i != n)
					bl[i]--;
				bl[i - size]++;
				if (i - size > 0)
					wh[i - size - 1]++;
			}
		}
	}

	if (!hi[i - 1])
	{
		if (DP(i - 1, j))
		{
			b = true;
			wh[i - 1]++;
		}
	}
	seT[i][j] = true;
	return dp[i][j] = b;
}

string solve_puzzle(string s, vector<int> c)
{
	n = s.size();
	k = c.size();

	cl = c;

	hi = vector<bool>(n);
	numWhite = vector<int>(n);
	seT = dp = vector<vector<bool>>(n + 1, vector<bool>(k + 1));

	for (int i = 0; i < n; i++)
	{
		numWhite[i] += numWhite[max(i - 1, 0)];
		if (s[i] == 'X')
			hi[i] = true;
		if (s[i] == '_')
			numWhite[i]++;
	}

	wh = bl = vector<int>(n);

	DP(n, k);

	int black = 0;

	string out;

	for (int i = 0; i < n; i++)
	{
		black += bl[i];

		if (black && wh[i])
			out.push_back('?');
		else if (black)
			out.push_back('X');
		else
			out.push_back('_');
	}
	return out;
}

#ifdef _DEBUG

signed main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int n, k;
	cin >> n >> k;

	string s;
	cin >> s;

	vector<int> blub(k);

	for (int &x : blub)
		cin >> x;

	cout << solve_puzzle(s, blub);
}

#endif

• 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