Submission #116090

#	Time	Username	Problem	Language	Result	Execution time	Memory
116090		davitmarg	Paint By Numbers (IOI16_paint)	C++17	80 / 100	9 ms	2560 KiB

paint

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <ctype.h>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

int n,k;
string s,ans;
vector<int> a;
bool pr[102][102][102], sf[102][102][102];

int Main()
{
	k = a.size();
	a.PB(0);
	reverse(all(a));
	a.PB(0);
	reverse(all(a));

	pr[0][0][1] = 1;

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			for (int p = 1; p <= k+1; p++)
			{
				if (a[p] < j || pr[i][j][p] == 0)
					continue;
				if (s[i + 1] == 'X' || s[i + 1] == '.')
					pr[i + 1][j + 1][p] |= (j + 1 <= a[p]);
				if (s[i + 1] == '_' || s[i + 1] == '.')
				{
					pr[i + 1][0][p+1] |= (j == a[p]);
					pr[i + 1][0][p] |= (j == 0);
				}
			}

	sf[n+1][0][k] = 1;
	for (int i = n+1; i >= 1; i--)
		for (int j = 0; j <= n; j++)
			for (int p = k; p >= 0; p--)
			{
				if (a[p] < j || sf[i][j][p] == 0)
					continue;
				if (s[i - 1] == 'X' || s[i - 1] == '.')
					sf[i - 1][j + 1][p] |= (j + 1 <= a[p]);
				if (s[i - 1] == '_' || s[i - 1] == '.')
				{
					if(p-1>=0)
						sf[i - 1][0][p - 1] |= (j == a[p]);
					sf[i - 1][0][p] |= (j == 0);
				}
			}
	ans = s;
	for (int i = 0; i <= n; i++)
	{
		if (s[i] != '.')
		{
			ans[i] = s[i];
			continue;
		}
		int cnt[2] = { 0,0 };
		for (int j = 0; j <= n; j++)
			for (int p = 1; p <= k+1; p++)
			{
				if (a[p]<j || !pr[i][j][p])
					continue;
				cnt[(bool)j] += sf[i + 1][a[p]-j][p];
				if(j==0)
					cnt[(bool)j] += sf[i + 1][0][p-1];
			}
		if (cnt[0] && cnt[1])
			ans[i] = '?';
		else if (cnt[0])
			ans[i] = '_';
		else
			ans[i] = 'X';
	}
	ans.pop_back();
	reverse(all(ans));
	ans.pop_back();
	reverse(all(ans));

	return 0;
}

string solve_puzzle(string S,vector<int> c)
{
	a = c;
	s = "_"+S+"_";
	n = S.length();
	Main();
	return ans;
}

#ifdef death

int main()
{
	int K;
	string S;
	vector<int> C;
	cin >> S >> K;
	while (K--)
	{
		C.PB(0);
		cin >> C.back();
	}
	cout << solve_puzzle(S, C) << endl;
	return 0;
}

#endif

/*

.X........
1
3

*/

• 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