Submission #873035

#	Time	Username	Problem	Language	Result	Execution time	Memory
873035		aykhn	Paint By Numbers (IOI16_paint)	C++17	80 / 100	5 ms	4700 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<int> prefX, pref_;

int getX(int l, int r)
{
	r = min(r, n - 1);
	if (l > 0) return prefX[r] - prefX[l - 1];
	return prefX[r];
}

int get_(int l, int r)
{
	r = min(r, n - 1);
	if (l > 0) return pref_[r] - pref_[l - 1];
	return pref_[r];
}

string solve_puzzle(string s, vector<int> c) 
{
	n = s.length();
	k = c.size();
	vector<vector<array<int, 2>>> dp1(n + 1, vector<array<int, 2>> (k + 1, {0, 0}));
	vector<vector<array<int, 2>>> dp2 = dp1;
	prefX.assign(n + 1, 0);
	pref_.assign(n + 1, 0);
	for (int i = 0; i < n; i++)
	{
		if (i) 
		{
			prefX[i] = prefX[i - 1];
			pref_[i] = pref_[i - 1];
		}
		prefX[i] += (s[i] == 'X');
		pref_[i] += (s[i] == '_');
	}
	for (int i = 0; i < n; i++)
	{
		if (s[i] == '.' || s[i] == 'X')
		{
			int cnt_ = get_(i, i + c[0] - 1);
			int cntX = (!i ? 0 : getX(0, i - 1));
			int flag = 1;
			if (1 == c.size() && i + c[0] < n && getX(i + c[0], n - 1)) flag = 0;
			if (!(!flag || cntX || cnt_ || i + c[0] - 1 >= n)) 
			{
				if (i) dp1[i][0][0] = dp1[i - 1][0][1];
				else dp1[i][0][0] = 1;
			}
		}
		if (s[i] == '.' || s[i] == '_')
		{
			int cntX = (!i ? 0 : getX(0, i - 1));
			if (cntX) continue;
			if (i) dp1[i][0][1] = dp1[i - 1][0][1];
			else dp1[i][0][1] = 1;
		}
	}
	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j < k; j++)
		{
			if (s[i] == '.' || s[i] == 'X')
			{
				int cnt_ = get_(i, i + c[j] - 1);
				int flag = 1;
				if (j == k - 1 && i + c[j] < n && getX(i + c[j], n - 1)) flag = 0;
				if (!(!flag || cnt_ || i + c[j] - 1 >= n)) 
				{
					dp1[i][j][0] = dp1[i - 1][j][1];
				}
			}
			if (s[i] == '.' || s[i] == '_')
			{
				dp1[i][j][1] = dp1[i - 1][j][1];
				if (i - c[j - 1] < 0) continue;
				dp1[i][j][1] += dp1[i - c[j - 1]][j - 1][0];
			}
		}
	}
	//-----
	for (int i = n - 1; i >= 0; i--)
	{
		if (s[i] == '.' || s[i] == 'X')
		{
			int cnt_ = get_(i, i + c[k - 1] - 1);
			int cntX = (i + c[k - 1] >= n ? 0 : getX(i + c[k - 1], n - 1));
			int flag = 1;
			if (1 == c.size() && i && getX(0, i - 1)) flag = 0;
			if (!(!flag || cntX || cnt_ || i + c[k - 1] - 1 >= n)) 
			{
				if (i + c[k - 1] < n) dp2[i][k - 1][0] = dp2[i + c[k - 1]][k - 1][1];
				else dp2[i][k - 1][0] = 1;
			}
		}
		if (s[i] == '.' || s[i] == '_')
		{
			int cntX = (i == n - 1 ? 0 : getX(i + 1, n - 1));
			if (cntX) continue;
			if (i != n - 1) dp2[i][k - 1][1] = dp2[i + 1][k - 1][1];
			else dp2[i][k - 1][1] = 1;
		}
	}
	for (int i = n - 2; i >= 0; i--)
	{
		for (int j = k - 2; j >= 0; j--)
		{
			if (s[i] == '.' || s[i] == 'X')
			{
				int cnt_ = get_(i, i + c[j] - 1);
				int flag = 1;
				if (!j && i && getX(0, i - 1)) flag = 0;
				if (!(!flag || cnt_ || i + c[j] - 1 >= n)) 
				{
					if (i + c[j] < n) dp2[i][j][0] = dp2[i + c[j]][j][1];
				}
			}
			if (s[i] == '.' || s[i] == '_')
			{
				dp2[i][j][1] = dp2[i + 1][j][1];
				dp2[i][j][1] += dp2[i + 1][j + 1][0];
			}
		}
	}
	vector<int> exl(n + 1, 0), exr(n + 1, 0);
	for (int i = 1; i < n; i++)
	{
		exl[i] = exl[i - 1];
		if (i - c[k - 1] >= 0) exl[i] += dp1[i - c[k - 1]][k - 1][0];
	}
	for (int i = n - 2; i >= 0; i--)
	{
		exr[i] = exr[i + 1] + dp2[i + 1][0][0];
	}
	// for (int j = 0; j < k; j++)
	// {
	// 	for (int i = 0; i < n; i++)
	// 	{
	// 		cout << dp1[i][j][1] << ' ';
	// 	}
	// 	cout << '\n';
	// }
	// for (int i = 0; i < n; i++) cout << exl[i] << ' ';
	// cout << "\n\n";
	// for (int i = 0; i < n; i++) cout << exr[i] << ' ';
	// cout << '\n';
	// for (int j = 0; j < k; j++)
	// {
	// 	for (int i = 0; i < n; i++)
	// 	{
	// 		cout << dp2[i][j][1] << ' ';
	// 	}
	// 	cout << '\n';
	// }
	// cout << '\n';
	int all = 0;
	vector<int> pref(n + 1, 0), cnt(n + 1, 0);
	for (int i = 0; i < n; i++)
	{
		all += dp1[i][k - 1][0];
		cnt[i] += exl[i] * dp2[i][k - 1][1];
		for (int j = 0; j < k; j++)
		{
			int x = dp1[i][j][0] * dp2[i][j][0];
			pref[i] += x;
			if (i + c[j] < n) pref[i + c[j]] -= x;
			if (!j) x = exr[i] * dp1[i][j][1];
			else x = dp1[i][j][1] * dp2[i][j - 1][1];
			cnt[i] += x;
		}
	}
	// cout << all << endl;
	for (int i = 1; i < n; i++) pref[i] += pref[i - 1];
	string res = "";
	for (int i = 0; i < n; i++)
	{
		// cout << cnt[i] << ' ';
		if (pref[i] == all) res.push_back('X');
		else if (cnt[i] == all) res.push_back('_');
		else res.push_back('?');
	}
	// cout << '\n';
	return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10