Submission #344893

#	Time	Username	Problem	Language	Result	Execution time	Memory
344893		ogibogi2004	Paint By Numbers (IOI16_paint)	C++14	100 / 100	642 ms	68756 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
const int MAXK=128;
bool dp[MAXN][MAXK];
bool calculated[MAXN][MAXK];
bool xallowed[MAXN][MAXK];
bool yallowed[MAXN][MAXK];
bool xa[MAXN],ya[MAXN];
int b[MAXK],k;
int pref[MAXN];
string s1;
int get_pref(int x)
{
	if(x<0)return 0;
	return pref[x];
}
vector<pair<int,int> >aveei;
bool dfs(int idx,int cntblocks)
{
	//aveei.push_back({idx,cntblocks});
	if(calculated[idx][cntblocks])return dp[idx][cntblocks];
	calculated[idx][cntblocks]=1;
	if(idx>=s1.size()-3&&cntblocks==k)
	{
		return dp[idx][cntblocks]=1;
	}
	else if(idx>=s1.size()-3)
	{
		return dp[idx][cntblocks]=0;
	}
	if(s1[idx]=='_'||s1[idx]=='.')
	{
		bool xd=dfs(idx+1,cntblocks);
		//cout<<idx<<" "<<cntblocks<<" => "<<idx+1<<" "<<xd<<endl;
		if(xd)
		{
			ya[idx]=1;
			dp[idx][cntblocks]=1;
		}
	}
	if(cntblocks<k)
	{
		if(s1[idx]=='X'||s1[idx]=='.')
		{
			int nxt=idx+b[cntblocks+1]-1;
			if(nxt<s1.size()-3&&get_pref(nxt)-get_pref(idx-1)==0)
			{
				if(s1[nxt+1]!='X')
				{
					bool xd=dfs(nxt+2,cntblocks+1);
					//cout<<idx<<" "<<cntblocks<<" -> "<<nxt<<" "<<xd<<endl;
					if(xd)
					{
						for(int j=idx;j<=nxt;j++)xa[j]=1;
						ya[nxt+1]=1;
						dp[idx][cntblocks]=1;
					}
				}
			}
		}
	}
	return dp[idx][cntblocks];
}
/*void dfs(int idx,int cntblocks)
{
	if(idx<0)return;
	if(yallowed[idx][cntblocks]&&dp[idx-1][cntblocks]==1)
	{
		ya[idx]=1;
		dfs(idx-1,cntblocks);
	}
	if(idx-b[cntblocks]>=-1)
	{
		if(xallowed[idx][cntblocks])
		{
			if(get_pref(idx)-get_pref(idx-b[cntblocks])==0&&(idx-b[cntblocks]==-1||s1[idx-b[cntblocks]]!='X'))
			{
				if(idx-b[cntblocks]-1<0||dp[idx-b[cntblocks]-1][cntblocks-1])
				{
					for(int j=idx;j>idx-b[cntblocks]&&j>=0;j--)xa[j]=1;
					dfs(idx-b[cntblocks]-1,cntblocks-1);
				}
			}
		}
	}
}*/
string solve_puzzle(string s,vector<int> c) {
    //return "";
    k=c.size();
    s1=s;
    reverse(s1.begin(),s1.end());
    s1+="___";
    reverse(s1.begin(),s1.end());
    s1+="___";
    for(int i=0;i<c.size();i++)b[i+1]=c[i];
	for(int i=0;i<s1.size();i++)
	{
		pref[i]=get_pref(i-1);
		if(s1[i]=='_')pref[i]++;
	}
    /*for(int i=0;i<s.size();i++)
    {
		if(s[i]=='X')
		{
			for(int j=0;j<c.size();j++)
			{
				if(i-c[j]+1<0)continue;
				if(i-c[j]<=0||dp[i-c[j]-1][j])
				{
					if(get_pref(i)-get_pref(i-c[j])==0&&(i-c[j]<0||s[i-c[j]]!='X'))
					{
						dp[i][j+1]=1;
						xallowed[i][j+1]=1;
					}
				}
			}
		}
		else if(s[i]=='_')
		{
			for(int j=0;j<=c.size();j++)
			{
				if(dp[i-1][j])
				{
					dp[i][j]=1;
					yallowed[i][j]=1;
				}
			}
		}
		else
		{
			for(int j=0;j<=c.size();j++)
			{
				if(dp[i-1][j])
				{
					dp[i][j]=1;
					yallowed[i][j]=1;
				}
			}
			for(int j=0;j<c.size();j++)
			{
				if(i-c[j]+1<0)continue;
				if(i-c[j]<=0||dp[i-c[j]-1][j])
				{
					if(get_pref(i)-get_pref(i-c[j])==0&&(i-c[j]<0||s[i-c[j]]!='X'))
					{
						dp[i][j+1]=1;
						xallowed[i][j+1]=1;
					}
				}
			}
		}
	}
	dfs(s.size()-1,c.size());*/
	dfs(0,0);
	string s2="";
	for(int i=3;i<s1.size()-3;i++)
	{
		if(xa[i])
		{
			if(ya[i])s2+="?";
			else s2+="X";
		}
		else s2+="_";
	}
	/*for(auto xd:aveei)
	{
		cout<<xd.first<<" "<<xd.second<<" "<<dp[xd.first][xd.second]<<endl;
	}
	cout<<s2<<endl;*/
	return s2;
}

Compilation message (stderr)

paint.cpp: In function 'bool dfs(int, int)':
paint.cpp:25:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  if(idx>=s1.size()-3&&cntblocks==k)
      |     ~~~^~~~~~~~~~~~~
paint.cpp:29:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  else if(idx>=s1.size()-3)
      |          ~~~^~~~~~~~~~~~~
paint.cpp:48:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    if(nxt<s1.size()-3&&get_pref(nxt)-get_pref(idx-1)==0)
      |       ~~~^~~~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i=0;i<c.size();i++)b[i+1]=c[i];
      |                 ~^~~~~~~~~
paint.cpp:98:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for(int i=0;i<s1.size();i++)
      |              ~^~~~~~~~~~
paint.cpp:158:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |  for(int i=3;i<s1.size()-3;i++)
      |              ~^~~~~~~~~~~~

• 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