Submission #292701

#	Time	Username	Problem	Language	Result	Execution time	Memory
292701		VodkaInTheJar	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2053 ms	78320 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];
vector <pair <int, int> > shit;
int max_r[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))
	{
		max_r[pos-c[k]] = max(max_r[pos-c[k]], pos-1);
		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]++;	
	}
	
	for (int i = 0; i < (int)s.size(); i++)
	max_r[i] = -1; 
	
	f((int)s.size()-1, (int)c.size()-1);
	dfs((int)s.size()-1, (int)c.size()-1);

	for (int i = 0; i < (int)s.size(); i++)
	if (max_r[i] >= i)
	shit.push_back({i, max_r[i]});
	
	int max_r = -1;
	for (auto i: shit)
	{
		if (i.second <= max_r)
		continue; 
		
		if (i.first > max_r)
		{
			for (int j = i.first; j <= i.second; j++)
			can_black[j] = true; 
			
			max_r = i.second; 
		}
		
		else 
		{
			for (int j = max_r + 1; j <= i.second; j++)
			can_black[j] = true;
			
			max_r = i.second;
		}
	}
	
	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