제출 #69137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69137		Sa1378	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2078 ms	37764 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N ((int)201*1000)
#define K ((int)101)

int n,k;
int lft_[N],rght_[N];
bool dpl[N][K],dpr[N][K];

string solve_puzzle(string s, vector<int> c)
{
	n=s.size();k=c.size();
	s='.'+s+'.';
	lft_[0]=0;
	for(int i=1;i<=n;i++)
		lft_[i]=max(lft_[i-1],(s[i]=='_'?i:0));
	rght_[n+1]=n+1;
	for(int i=n;i>=1;i--)
		rght_[i]=min(rght_[i+1],(s[i]=='_'?i:n+1));
	dpl[0][0]=dpr[n+1][k+1]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=k;j++)
		{
			if(s[i]!='X' && dpl[i-1][j]){dpl[i][j]=1;continue;}
			if(!j || i<c[j-1] || lft_[i]>=i-c[j-1]+1 || s[i-c[j-1]]=='X')continue;
		//	if(i==6 && j==2)cout<<"hir\n";
			dpl[i][j]=((i-c[j-1]-1)>=0)?dpl[i-c[j-1]-1][j-1]:(j==1);
		}
	for(int i=n;i>=1;i--)
		for(int j=1;j<=k+1;j++)
		{
			if(s[i]!='X' && dpr[i+1][j]){dpr[i][j]=1;continue;}
			if(j==k+1 || n-i+1<c[j-1] || rght_[i]<=i+c[j-1]-1 || s[i+c[j-1]]=='X')continue;
			dpr[i][j]=((i+c[j-1]+1)<=n+1)?dpr[i+c[j-1]+1][j+1]:(j==k);
		}
	string ans="";
	for(int i=1;i<=n;i++)
	{
		if(s[i]!='.'){ans+=s[i];continue;}
		int res=0;
		for(int j=0;j<=k;j++)
			if(dpl[i-1][j] && dpr[i+1][j+1])
			{
				res=1;
				break;
			}
		for(int j=1;j<=k;j++)
		{
			int l=max(i-c[j-1]+1,lft_[i]+1),r=l+c[j-1]-1;
			while(l<=i)
			{
				if(r>n || rght_[i]<=r)break;
				if(l<1 || s[l-1]=='X' || s[r+1]=='X' || (l-2<0 && j!=1) || (r+2>n+1 && j!=k)){l++;r++;continue;}
				if((l-2<0 || dpl[l-2][j-1]) && (r+2>n+1 || dpr[r+2][j+1])){res|=2;break;}
				l++;r++;
			}
	//		if(i==4)cout<<j<<" "<<l<<" "<<r<<" "<<dpl[l-2][j-1]<<" "<<dpr[r+2][j+1]<<"\n";
			if(res>=2)break;
		}
		if(res==1)ans+='_';
		if(res==2)ans+='X';
		if(res==3)ans+='?';
	}
    return ans;
}

• 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: 0 / 10