Submission #1304854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304854		neonglitch	Paint By Numbers (IOI16_paint)	C++20	100 / 100	386 ms	83480 KiB

paint

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=2e5+1,K=101;
struct solver{
	int mx[N];
	bool dp[N][K][2];
	solver()
	{
		
	}
	bool check(string& s,vector<int>& c)
	{
		int n=s.size(),k=c.size();
		for(int i=0;i<=n;i++)
		{
			for(int j=0;j<=k;j++)
			{
				dp[i][j][0]=dp[i][j][1]=0;
			}
		}
		mx[n]=n;
		for(int i=n-1;i>=0;i--)
		{
			if(s[i]!='_')
			{
				mx[i]=mx[i+1];
			}
			else{
				mx[i]=i;				
			}
			// exc
		}
		dp[0][0][0]=1;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<=k;j++)
			{
				dp[i+1][j][0]|=((dp[i][j][0]|dp[i][j][1])&(s[i]!='X')); // cell is not black and we can fix before it ending in b or w
				if(j<k and i+c[j] <= mx[i])
				{
					dp[i+c[j]][j+1][1]|=(dp[i][j][0]);
				}
			}
		}
		return dp[n][k][0]|dp[n][k][1];
	}
};

string solve_puzzle(string s,vector<int> c)
{
	int n=s.size();
	int k=c.size();
	string ans;
	
	solver ff;
	solver ss;
	
	ff.check(s,c);
	reverse(begin(s),end(s));
	reverse(begin(c),end(c));
	ss.check(s,c);
	
	reverse(begin(s),end(s));
	reverse(begin(c),end(c));
	
	vector<int> cbw(n+1),cbb(n+1);
	for(int i=0;i<n;i++)
	{
		if(s[i]!='.')
		{
			
		}
		else{
			for(int j=0;j<=k;j++)
			{
				if(ff.dp[i+1][j][0] && ss.dp[n-i][k-j][0])
				{
					cbw[i]=1;
				}					
			}
		}
	}
	for(int j=0;j<k;j++)
	{
		for(int i=0;i+c[j]<=n;i++)
		{
			// let index i,i+1,..,i+c[j]-1 a block and try to solve it
			if(i+c[j]<=ff.mx[i] && ff.dp[i][j][0] && ss.dp[n-i-c[j]][k-1-j][0])
			{
				cbb[i]++;
				cbb[i+c[j]]--;
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		if(i)cbb[i]+=cbb[i-1];
		if(s[i]!='.')
		{
			ans+=s[i];
		}
		else{
			if(cbb[i]>0 and cbw[i]>0)ans+='?';
			else if(cbb[i]>0)ans+='X';
			else ans+='_';
		}
	}
	return ans;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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