Submission #112136

#	Time	Username	Problem	Language	Result	Execution time	Memory
112136		Pajaraja	Paint By Numbers (IOI16_paint)	C++17	100 / 100	305 ms	44828 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define MAXN 400007
#define MAXK 107
using namespace std;
bool dpl[MAXK][MAXN],dpr[MAXK][MAXN],mb[MAXN],mc[MAXN];
int nz[MAXN],lw[MAXN],nw[MAXN];
std::string solve_puzzle(std::string s, std::vector<int> c) 
{
	int n=s.size()+2,k=c.size();
	for(int i=2;i<n;i++)
	{
		if(s[i-2]=='X') nz[i]=0;
		if(s[i-2]=='_') nz[i]=1;
		if(s[i-2]=='.') nz[i]=2;
	}
	nz[1]=nz[n]=1;
	dpl[0][0]=true;
	for(int i=1;i<=n;i++) for(int j=0;j<=k;j++)
	{
		if(nz[i]) dpl[j][i]=dpl[j][i-1];
		if(nz[i]==1) lw[i]=i;
		else lw[i]=lw[i-1];
		if(j>0 && i>=lw[i]+c[j-1] && dpl[j-1][i-c[j-1]-1] && nz[i-c[j-1]]) dpl[j][i]=true;
	}
	dpr[k+1][n+1]=true;
    for(int i=n;i>0;i--) for(int j=k+1;j>0;j--)
	{
		if(nz[i]) dpr[j][i]=dpr[j][i+1];
		if(nz[i]==1) nw[i]=i;
		else nw[i]=nw[i+1];
		if(j<=k && i+c[j-1]<=nw[i] && dpr[j+1][i+c[j-1]+1] && nz[i+c[j-1]]) dpr[j][i]=true;
	}
	for(int i=2;i<n;i++) for(int j=0;j<=k;j++) if(dpl[j][i-1] && dpr[j+1][i+1]) mb[i-2]=true;
	for(int j=1;j<=k;j++)
	{
		int nd=1;
		for(int i=2;i<n;i++) 
		{
			if(dpl[j-1][i-2] && dpr[j+1][i+c[j-1]+1] && nz[i-1] && nz[i+c[j-1]] && nw[i]>=i+c[j-1]) nd=i+c[j-1]-1;
			if(i<=nd) mc[i-2]=true;
		}
	}
	string res="";
	for(int i=0;i<n;i++)
	{
		if(s[i]!='.') res+=s[i];
		else
		{
			if(mb[i] && mc[i]) res+='?';
			if(mb[i] && !mc[i]) res+='_';
			if(!mb[i] && mc[i]) res+='X';
		}
	}
	return res;
}

• 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