Submission #873038

#	Time	Username	Problem	Language	Result	Execution time	Memory
873038		aykhn	Paint By Numbers (IOI16_paint)	C++17	100 / 100	516 ms	335140 KiB

paint

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

using namespace std;
typedef long long ll;

const ll mod = 1e9 + 7;

ll n, k;
int dp1[200005][105][2], dp2[200005][105][2];
int prefX[200005], pref_[200005], exl[200005], exr[200005], pref[200005], cnt[200005];
string res = "";

ll add(ll a, ll b)
{
	return (a + b) % mod;
}

ll mult(ll a, ll b)
{
	return (a * b) % mod;
}

ll sub(ll a, ll b)
{
	return (a - b + 10*mod) % mod;
}

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

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


string solve_puzzle(string s, vector<int> c) 
{
	n = s.length();
	k = c.size();
	for (ll 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 (ll i = 0; i < n; i++)
	{
		if (s[i] == '.' || s[i] == 'X')
		{
			ll cnt_ = get_(i, i + c[0] - 1);
			ll cntX = (!i ? 0 : getX(0, i - 1));
			ll 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] == '_')
		{
			ll 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 (ll i = 1; i < n; i++)
	{
		for (ll j = 1; j < k; j++)
		{
			if (s[i] == '.' || s[i] == 'X')
			{
				ll cnt_ = get_(i, i + c[j] - 1);
				ll 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] = add(dp1[i][j][1], dp1[i - c[j - 1]][j - 1][0]);
			}
		}
	}
	//-----
	for (ll i = n - 1; i >= 0; i--)
	{
		if (s[i] == '.' || s[i] == 'X')
		{
			ll cnt_ = get_(i, i + c[k - 1] - 1);
			ll cntX = (i + c[k - 1] >= n ? 0 : getX(i + c[k - 1], n - 1));
			ll 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] == '_')
		{
			ll 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 (ll i = n - 2; i >= 0; i--)
	{
		for (ll j = k - 2; j >= 0; j--)
		{
			if (s[i] == '.' || s[i] == 'X')
			{
				ll cnt_ = get_(i, i + c[j] - 1);
				ll 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] = add(dp2[i][j][1], dp2[i + 1][j + 1][0]);
			}
		}
	}
	for (ll i = 1; i < n; i++)
	{
		exl[i] = exl[i - 1];
		if (i - c[k - 1] >= 0) exl[i] = add(exl[i], dp1[i - c[k - 1]][k - 1][0]);
	}
	for (ll i = n - 2; i >= 0; i--)
	{
		exr[i] = add(exr[i + 1], dp2[i + 1][0][0]);
	}
	// for (ll j = 0; j < k; j++)
	// {
	// 	for (ll i = 0; i < n; i++)
	// 	{
	// 		cout << dp1[i][j][1] << ' ';
	// 	}
	// 	cout << '\n';
	// }
	// for (ll i = 0; i < n; i++) cout << exl[i] << ' ';
	// cout << "\n\n";
	// for (ll i = 0; i < n; i++) cout << exr[i] << ' ';
	// cout << '\n';
	// for (ll j = 0; j < k; j++)
	// {
	// 	for (ll i = 0; i < n; i++)
	// 	{
	// 		cout << dp2[i][j][1] << ' ';
	// 	}
	// 	cout << '\n';
	// }
	// cout << '\n';
	ll all = 0;
	for (ll i = 0; i < n; i++)
	{
		all = add(all, dp1[i][k - 1][0]);
		cnt[i] = add(cnt[i], mult(exl[i], dp2[i][k - 1][1]));
		for (ll j = 0; j < k; j++)
		{
			ll x = mult(dp1[i][j][0], dp2[i][j][0]);
			pref[i] = add(pref[i], x);
			if (i + c[j] < n) pref[i + c[j]] = sub(pref[i + c[j]], x);
			if (!j) x = mult(exr[i], dp1[i][j][1]);
			else x = mult(dp1[i][j][1], dp2[i][j - 1][1]);
			cnt[i] = add(cnt[i], x);
		}
	}
	// cout << all << endl;
	for (ll i = 1; i < n; i++) pref[i] = add(pref[i], pref[i - 1]);
	for (ll 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: 10 / 10
• Subtask 7: 10 / 10