Submission #1304843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304843		neonglitch	Paint By Numbers (IOI16_paint)	C++20	80 / 100	4 ms	576 KiB

paint

#include <iostream>
#include <vector>
using namespace std;
const int N=105,K=105;
int mx[N];
bool dp[N][K][2];
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;
		}
	}
	for(int i=0;i<n;i++)
	{
		mx[i]=i;
		while(mx[i]<n and s[mx[i]]!='_' )mx[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();
	string ans;
	for(int i=0;i<n;i++)
	{
		if(s[i]!='.')
		{
			ans+=s[i];
		}
		else{
			s[i]='_';
			bool wh=check(s,c);
			s[i]='X';
			bool bk=check(s,c);
			s[i]='.';
			if(wh && bk)
			{
				ans+='?';
			}
			else if(wh){
				ans+='_';
			}
			else{
				ans+='X';
			}
		}
	}
	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: 0 / 10
• Subtask 7: 0 / 10