Submission #986392

#	Time	Username	Problem	Language	Result	Execution time	Memory
986392		Pyqe	Paint By Numbers (IOI16_paint)	C++17	100 / 100	374 ms	18524 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

long long n,m,ps[200069];
bitset<269> dp[2][200069];

long long qr(long long lh,long long rh)
{
	if(lh>rh)
	{
		swap(lh,rh);
	}
	return ps[rh]-ps[lh-1];
}

string solve_puzzle(string s,vector<int> a)
{
	long long i,j,ii,u,tg;
	
	n=s.length();
	m=a.size();
	for(i=1;i<=n;i++)
	{
		ps[i]=ps[i-1]+(s[i-1]=='_');
	}
	for(ii=0;ii<2;ii++)
	{
		u=!ii*2-1;
		dp[ii][(n+1)*ii][m*2*ii]=1;
		for(i=1+(n-1)*ii;i&&i<=n;i+=u)
		{
			for(j=0;j<=m*2;j++)
			{
				if(j%2==0)
				{
					if(s[i-1]!='X')
					{
						dp[ii][i][j]=dp[ii][i-u][j];
						if(j-u>=0&&j-u<=m*2)
						{
							dp[ii][i][j]=dp[ii][i][j]|dp[ii][i-u][j-u];
						}
					}
				}
				else
				{
					tg=i-a[j/2]*u;
					if(tg>=0&&tg<=n+1&&!qr(i,tg+u))
					{
						dp[ii][i][j]=dp[ii][tg][j-u];
					}
				}
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		ps[i]=0;
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m*2;j+=2)
		{
			if(dp[0][i][j]&&dp[1][i+1][j+1])
			{
				ps[i-a[j/2]+1]++;
				ps[i+1]--;
			}
		}
	}
	s="";
	for(i=1;i<=n;i++)
	{
		ps[i]+=ps[i-1];
		if(!ps[i])
		{
			s+='_';
		}
		else
		{
			for(j=0;j<=m*2;j+=2)
			{
				if(dp[0][i][j]&&dp[1][i][j])
				{
					j=-1;
					break;
				}
			}
			if(j!=-1)
			{
				s+='X';
			}
			else
			{
				s+='?';
			}
		}
	}
	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