Submission #292686

#	Time	Username	Problem	Language	Result	Execution time	Memory
292686		VodkaInTheJar	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2069 ms	76016 KiB

paint

#include <bits/stdc++.h>
 
using namespace std;

const int maxn = 200003;
const int maxk = 103;

string s;
vector <int> c; 
int pr[maxn];
pair <bool, bool> dp[maxn][maxk];
bool f(int pos, int k)
{
	if (pos == 0)
	{
		if (k == -1)
		return true;
		
		return false; 
	}
	
	if (k < -1)
	return false; 
	
	if (dp[pos][k+1].second)
	return dp[pos][k+1].first;
	
	dp[pos][k+1] = {false, true};
	
	if (k != -1)
	if (pos-c[k]-1 >= 0)
	if (s[pos-c[k]-1] != 'X')
	if (pr[pos-1] - pr[pos-c[k]-1] == 0)
	if (f(pos-c[k]-1, k-1))
	dp[pos][k+1].first = true; 
	
	if (s[pos-1] != 'X')
	if (f(pos-1, k))
	dp[pos][k+1].first = true; 
	
	return dp[pos][k+1].first;
}

bool used[maxn][maxk];
bool can_white[maxn], can_black[maxn];
void dfs(int pos, int k)
{
	if (pos == 0)
	return;
	
	if (used[pos][k+1])
	return;
	
	used[pos][k+1] = true;
	can_white[pos] = true; 
	if (s[pos-1] != 'X')
	if (f(pos-1, k))
	dfs(pos-1, k);
	
	if (k != -1)
	if (pos-c[k]-1 >= 0)
	if (s[pos-c[k]-1] != 'X')
	if (pr[pos-1] - pr[pos-c[k]-1] == 0)
	if (f(pos-c[k]-1, k-1))
	{
		for (int j = pos-c[k]; j <= pos-1; j++)
		can_black[j] = true;
		
		dfs(pos-c[k]-1, k-1);
	}
}

string solve_puzzle(string _s, vector <int> _c)
{
	s += "_";
	s += _s;
	s += "_";
	
	c = _c; 
	
	if (s[0] == '_')
	pr[0]++;
		
	for (int i = 1; i < (int)s.size(); i++)
	{
		pr[i] = pr[i-1];
		if (s[i] == '_')
		pr[i]++;	
	}
	
	f((int)s.size()-1, (int)c.size()-1);
	dfs((int)s.size()-1, (int)c.size()-1);
	
	string ans; 
	for (int i = 0; i < (int)s.size()-2; i++)
	{
		if (can_black[i+1] && can_white[i+1])
		ans += "?";
		
		else 
		if (can_black[i+1])
		ans += "X";
		
		else 
		ans += "_";
	}
	
	return ans; 
}

/*
string s1;
int k1; 
vector <int> v1; 
int main()
{
	cin >> s1 >> k1;
	v1.resize(k1);
	for (int i = 0; i < k1; i++)
	cin >> v1[i];
	
	cout << solve_puzzle(s1, v1) << endl; 	
}
*/

• 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: 0 / 10