Submission #369704

#	Time	Username	Problem	Language	Result	Execution time	Memory
369704		Jasiekstrz	Paint By Numbers (IOI16_paint)	C++17	100 / 100	334 ms	88248 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"
#define fi first
#define se second
using namespace std;
bool ok[200010][110][2];
bool okk[200010][110][2];
int ch[200010];
string solve_puzzle(string s,vector<int> c)
{
	int n=s.size(),k=c.size(),a,b,i,j;
	a=-1;b=-n-10;
	for(i=0;i<n;i++)
	{
		if(s[i]=='_')
			a=i;
		if(s[i]=='X')
			b=i;
		if(b<0)
			ok[i][0][0]=true;
		for(j=1;j<=k;j++)
		{
			if(i>0 && s[i]!='X' && ok[i-1][j][0])
				ok[i][j][0]=true;
			if(a+c[j-1]<=i && s[i-c[j-1]]!='X' 
					&& ((i-c[j-1]-1<0 && j==1) || (i-c[j-1]-1>=0 && ok[i-c[j-1]-1][j-1][0])))
				okk[i][j][0]=ok[i][j][0]=true;
		}
	}
	a=n;b=2*n+10;
	for(i=n-1;i>=0;i--)
	{
		if(s[i]=='_')
			a=i;
		if(s[i]=='X')
			b=i;
		if(b>n)
			ok[i][k+1][1]=true;
		for(j=1;j<=k;j++)
		{
			if(i<n-1 && s[i]!='X' && ok[i+1][j][1])
				ok[i][j][1]=true;
			if(a-c[j-1]>=i && s[i+c[j-1]]!='X' 
					&& ((i+c[j-1]+1>=n && j==k) || (i+c[j-1]+1<n && ok[i+c[j-1]+1][j+1][1])))
				okk[i][j][1]=ok[i][j][1]=true;
		}
	}
	for(i=0;i<n;i++)
	{
		for(j=1;j<=k;j++)
		{
			if(okk[i][j][1] && okk[i+c[j-1]-1][j][0])
			{
				//cerr<<j<<" ["<<i<<","<<i+c[j-1]-1<<"]\n";
				ch[i]++;
				ch[i+c[j-1]]--;
			}
		}
	}
	for(i=0;i<n;i++)
	{
		if(i>0)
			ch[i]+=ch[i-1];
		bool wh=false,bl=(ch[i]>0);
		for(j=0;j<=k;j++)
		{
			if(s[i]!='X' && ((i==0 && j==0) || (i>0 && ok[i-1][j][0])) 
					&& ((i==n-1 && j==k) || (i<n-1 && ok[i+1][j+1][1])))
			{
				wh=true;
				break;
			}
		}
		if(!wh)
			s[i]='X';
		else if(!bl)
			s[i]='_';
		else
			s[i]='?';
	}
	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