Submission #292716

#	Time	Username	Problem	Language	Result	Execution time	Memory
292716		VodkaInTheJar	Paint By Numbers (IOI16_paint)	C++14	100 / 100	369 ms	53236 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];
bool dp[maxn][maxk];

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 (dp[pos-1][k+1])
	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 (dp[pos-c[k]-1][k])
	{
		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; 
	
	
	dp[0][0] = true;
	for (int i = 1; i < (int)s.size(); i++)
	for (int j = 0; j <= (int)c.size(); j++)
	{
		if (j != 0)
	    if (i-c[j-1]-1 >= 0)
	    if (s[i-c[j-1]-1] != 'X')
	    if (pr[i-1] - pr[i-c[j-1]-1] == 0)
	    if (dp[i-c[j-1]-1][j-1])
	    dp[i][j] = true;
	    
	    if (s[i-1] != 'X')
	    if (dp[i-1][j])
	    dp[i][j] = true;  
	}
	//f((int)s.size()-1, (int)c.size()-1);
	dfs((int)s.size()-1, (int)c.size()-1);

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