Submission #278436

#	Time	Username	Problem	Language	Result	Execution time	Memory
278436		ElyesChaabouni	Paint By Numbers (IOI16_paint)	C++14	100 / 100	966 ms	82808 KiB

paint

/*#pragma GCC optimize("O3")*/
#include<bits/stdc++.h>
//#include "paint.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define ordered_set tree<int, null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update>
#define eps 1e-9
#define MOD1 998244353
#define MOD2 1000000007
#define INV_10 299473306
#define INF 1000000000
#define PI 3.14159265358979323846
using namespace std;
string solve_puzzle(string s, vector<int> c)
//string solve_puzzle(string s, int k, int c[])
{
	int n=s.length();int k=c.size();
	int pr[n+1];
	int mi=n-1, ma=0;
	for(int i = 0;i < n+1; i++)
		pr[i]=0;
	int next_X[n+1], prev_x[n+1];
	next_X[n]=n-1;
	for(int i = s.length()-1; i >= 0; i--)
	{
		if(s[i]=='_')
			pr[i]=1;
		next_X[i]=mi;
		if(s[i]=='X')
		{
			mi=min(mi, i);
		}
		pr[i]+=pr[i+1];
	}
	for(int i = 0; i < n; i++)
	{
		prev_x[i]=ma;
		if(s[i]=='X')
			ma=i;
	}
	prev_x[n]=prev_x[n-1];
	/*for(int i = 0; i <= n; i++)
		cout << prev_x[i] << ' ';
	cout << '\n';*/
	int dp[n+1][k+1];
	for(int i = 0; i < n+1; i++)
		for(int j = 0; j < k+1; j++)
			dp[i][j]=0;
	dp[n][k]=1;
	for(int i = n-1; i >= 0; i--)
		dp[i][k]=1+dp[i+1][k];
	for(int i = k-1; i >= 0; i--)
	{
		for(int j = n-1; j >= 0; j--)
		{
			if(j+c[i]-1 < n && (i!=0 || j <= mi) && (i!=k-1 || j+c[i]-1 >= ma) && (j+c[i] == n || s[j+c[i]]!='X') && (j==0 || s[j-1]!='X') && pr[j]-pr[j+c[i]]==0 && ((i==k-1)||(j+c[i]+1 <= n && dp[j+c[i]+1][i+1]-dp[min(n-1, next_X[j+c[i]])+1][i+1] > 0)))
				dp[j][i]=1;
			dp[j][i]+=dp[j+1][i];
		}
	}
//	for(int i = 0; i <= k; i++)
//	{
//		for(int j = 0; j <= n; j++)
//		{
//			cout << dp[j][i] << ' ';
//		}
//		cout << '\n';
//	}
	/*for(int i = 0; i < n; i++)
	{
		if(s[i]=='X')
		{
			for(int j = 0; j < k-1; j++)
			{
				//cout << j << '\n';
				if(dp[0][j]-dp[max(i-c[j]+1, 0)][j] > 0 && dp[i+1][j+1]-dp[n][j+1] > 0)
					dp[i+1][j+1]=0;
			}
		}
	}
	for(int i = 0; i < k; i++)
	{
		int cu=100000000;
		for(int j = 0; j < n; j++)
		{
			cu=min(cu, dp[j][i]);
			dp[j][i]=cu;
		}
	}*/
	for(int i = 1; i < k; i++)
	{
		int sum=0;
		for(int j = n-1; j >= 0; j--)
		{
			int x=dp[j][i];
			dp[j][i]=dp[j+1][i];
			if(x==sum+1)
			{
				sum++;
				if(j-1-c[i-1] >= 0 && dp[max(0, prev_x[j]-c[i-1]+1)][i-1]-dp[j-1-c[i-1]+1][i-1] > 0)
					dp[j][i]++;
			}
		}
	}
	/*for(int i = k-2; i >= 0; i--)
	{
		int sum=0;
		for(int j = n-1; j >= 0; j--)
		{
			int x=dp[j][i];
			dp[j][i]=dp[j+1][i];
			if(x==sum+1)
			{
				sum++;
				if(j-1-c[i-1] >= 0 && dp[max(0, prev_x[j]-c[i-1]+1)][i-1]-dp[j-1-c[i-1]+1][i-1] > 0)
					dp[j][i]++;
			}
		}
	}*/
//	for(int i = 0; i <= k; i++)
//	{
//		for(int j = 0; j <= n; j++)
//		{
//			cout << dp[j][i] << ' ';
//		}
//		cout << '\n';
//	}
	/*int to_del[k+1];
	for(int i = 0; i < k+1; i++)
		to_del[i]=0;
	for(int i = 0; i < n; i++)
	{
		if(s[i]=='X')
		{
			for(int j = 0; j < k-1; j++)
			{
				//cout << j << '\n';
				if(dp[0][j]-dp[max(i-c[j]+1, 0)][j] > 0 && dp[i+1][j+1]-dp[n][j+1] > 0)
					to_del[j+1]=max(to_del[j+1], dp[i+1][j+1]);
			}
		}
	}
	for(int i = 0; i < k; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(dp[j][i] <= to_del[i])
				dp[j][i]=0;
		}
	}
	for(int i = 0; i < k; i++)
	{
		int x=0;
		for(int j = n-1; j >= 0; j--)
		{
			dp[j][i]=max(0, dp[j][i]-to_del[i]);
		}
	}*/
//	for(int i = 0; i <= k; i++)
//	{
//		for(int j = 0; j <= n; j++)
//		{
//			cout << dp[j][i] << ' ';
//		}
//		cout << '\n';
//	}
	int la=0;
	for(int i = 0; i < n; i++)
	{
		bool done=0;
//		cout << i << ' ';
		if(s[i]=='.')
		{
			for(int j = 0; j < k && !done; j++)
			{
				int pos=max(0, i-c[j]+1);
				if(dp[max(pos, prev_x[i]-c[j]+1)][j]-dp[i+1][j] > 0)
				{
//					cout << "not _ "  << j << ' ';
					done=1;
				}
			}
//			cout << done << ' ';
			if(!done)
			{
				s[i]='_';
			}
			else
			{
				done=0;
				//cout << 15611;
				int pos=max(max(i-c[k-1]+1, 0), la);
				if((dp[0][k-1]-dp[max(i-c[k-1]+1, 0)][k-1] > 0 && i!=0) || (dp[i+1][0]-dp[n][0] > 0 && i!=n-1))
				{
					done=1;
//					cout << i << ' ' << "here ";
//					cout << (dp[i+1][0]-dp[n][0] > 0 && i!=n-1) << '\n';
				}
				for(int j = 0; j < k-1 && !done && i!=0 && i!=n-1; j++)
				{
					if(dp[max(0, prev_x[i]-c[j]+1)][j]-dp[max(i-c[j]+1, 0)][j] > 0 && dp[i+1][j+1]-dp[min(n-1, next_X[i])+1][j+1] > 0)
					{
//						cout << i << ' ' << j << ' ';
						done=1;
					}
				}
				if(!done)
				{
					s[i]='X';
				}
				else
					s[i]='?';
			}
		}
//		cout << '\n';
	}
	return s;
}
/*int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	string s;
	cin >> s;
	int k;
	cin >> k;
	//vector<int>v;
	int v[k];
	for(int i = 0; i < k; i++)
	{
		int x;
		cin >> x;
		//v.push_back(x);
		v[i]=x;
	}
	cout << solve_puzzle(s, k, v) << '\n';
}*/
//size

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:192:9: warning: unused variable 'pos' [-Wunused-variable]
  192 |     int pos=max(max(i-c[k-1]+1, 0), la);
      |         ^~~

• 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