Submission #43901

#	Time	Username	Problem	Language	Result	Execution time	Memory
43901		faustaadp	Paint By Numbers (IOI16_paint)	C++17	100 / 100	937 ms	101792 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
#include <cstdlib>
ll n,k,i,p1[201010],p2[201010],C[110],j,mas[201010],kel[201010],hv;
char A[201010];
string S;
bool b1[110][201010],b2[110][201010],d1[110][201010],d2[110][201010];
bool depe1(ll aa,ll bb)
{
	if(aa==0)
	{
		if(bb<=0||p2[bb]==0)
			return 1;
		else
			return 0;
	}
	else
	if(!b1[aa][bb])
	{
		b1[aa][bb]=1;
		if(bb-C[aa]<0)
			d1[aa][bb]=0;
		else
		{
			if(A[bb]=='X')
			{
				if(p1[bb]-p1[bb-C[aa]]==0&&A[bb-C[aa]]!='X')
					d1[aa][bb]=depe1(aa-1,bb-C[aa]-1);
				else
					d1[aa][bb]=0;
			}
			else
			{
				if(p1[bb]-p1[bb-C[aa]]==0&&A[bb-C[aa]]!='X')
					d1[aa][bb]=depe1(aa-1,bb-C[aa]-1);
				d1[aa][bb]=d1[aa][bb]|depe1(aa,bb-1);
			}
		}
	}
	return d1[aa][bb];
}
bool depe2(ll aa,ll bb)
{
	if(aa>=k+1)
	{
		if(bb>n||p2[n]-p2[bb-1]==0)
			return 1;
		else
			return 0;
	}
	else
	if(!b2[aa][bb])
	{
		b2[aa][bb]=1;
		if(bb+C[aa]-1>n)
			d2[aa][bb]=0;
		else
		{
			if(A[bb]=='X')
			{
				if(p1[bb+C[aa]-1]-p1[bb-1]==0&&A[bb+C[aa]]!='X')
					d2[aa][bb]=depe2(aa+1,bb+C[aa]+1);
				else
					d2[aa][bb]=0;
			}
			else
			{
				if(p1[bb+C[aa]-1]-p1[bb-1]==0&&A[bb+C[aa]]!='X')
					d2[aa][bb]=depe2(aa+1,bb+C[aa]+1);
				d2[aa][bb]=d2[aa][bb]|depe2(aa,bb+1);
			}
		}
	}
	return d2[aa][bb];
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
	n=s.length();
	k=c.size();
	for(i=1;i<=n;i++)
	{
		A[i]=s[i-1];
		p1[i]=p1[i-1];
		p2[i]=p2[i-1];
		if(A[i]=='_')
			p1[i]++;
		if(A[i]=='X')
			p2[i]++;		
	}
	for(i=1;i<=k;i++)
		C[i]=c[i-1];
	for(i=1;i<=k;i++)
	{
		for(j=1;j+C[i]-1<=n;j++)
		{
			//cout<<i<<" "<<j<<" "<<j+C[i]-1<<" "<<depe1(i-1,j-2)<<" "<<depe2(i+1,j+C[i]+1)<<"\n";
			if(p1[j+C[i]-1]-p1[j-1]==0&&depe1(i-1,j-2)&&depe2(i+1,j+C[i]+1)&&(A[j-1]!='X')&&(A[j+C[i]]!='X'))
			{
				//cout<<i<<" "<<j<<" "<<j+C[i]-1<<"\n";
				mas[j]++;
				kel[j+C[i]-1]++;
			}
		}
	}
	for(i=0;i<n;i++)
		S+=".";
	for(i=1;i<=n;i++)
	{
		hv+=mas[i];
		if(hv)
			S[i-1]='X';
		hv-=kel[i];
	}
	//return S;
	for(i=0;i<=k;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(A[j]!='X'&&depe1(i,j-1)&&depe2(i+1,j+1))
			{
	//			cout<<i<<" "<<j<<"\n";
				if(S[j-1]=='X')
					S[j-1]='?';
				else
				if(S[j-1]=='.')
					S[j-1]='_';
			}
		}
	}
    return S;
}

• 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