Submission #266954

#	Time	Username	Problem	Language	Result	Execution time	Memory
266954		amiratou	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1387 ms	487056 KiB

paint

#pragma GCC optimize("O3")
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9+7,MOD2=(int)1e9+9;
typedef long long ll;
ll dp[200003][103],dp2[200003][103],cnt[200003],ans[200003][103];
string ANS;
 
string solve_puzzle(string s, vector<int> c) {
	int n=(int)s.size(),k=(int)c.size();
	for (int i = 1; i <= n; ++i)
	{
		if(s[i-1]=='_')cnt[i]++;
		cnt[i]+=cnt[i-1];
	}
	dp[n+1][k+1]=dp2[0][0]=1;
	for (int i = n; i >= 1; i--)
	{
		for (int j = 1; j <= k; ++j){
			if((i+c[j-1])<=(n+1) && ((i+c[j-1])==(n+1) || s[i+c[j-1]-1]!='X') && (i==1||(s[i-2]!='X')) && !(cnt[i+c[j-1]-1]-cnt[i-1])){
				if((i+c[j-1])==(n+1))dp[i][j]=(dp[i][j]+dp[i+c[j-1]][j+1])%MOD;
				else dp[i][j]=(dp[i][j]+dp[i+c[j-1]+1][j+1])%MOD;
			}
			if(s[i-1]!='X')dp[i][j]=(dp[i][j]+dp[i+1][j])%MOD;
		}
		if(s[i-1]!='X')dp[i][k+1]=(dp[i][k+1]+dp[i+1][k+1])%MOD;
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= k; ++j){
			if((i-c[j-1])>=0 && (!(i-c[j-1]) || s[i-c[j-1]-1]!='X') && (i==n||(s[i]!='X')) && !(cnt[i]-cnt[i-c[j-1]])){
				if(!(i-c[j-1]))dp2[i][j]=(dp2[i][j]+dp2[i-c[j-1]][j-1])%MOD;
				else dp2[i][j]=(dp2[i][j]+dp2[i-c[j-1]-1][j-1])%MOD;
			}	
			if(s[i-1]!='X')dp2[i][j]=(dp2[i][j]+dp2[i-1][j])%MOD;
		}
		if(s[i-1]!='X')dp2[i][0]=(dp2[i][0]+dp2[i-1][0])%MOD;
	}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= k; ++j){
			if((i+c[j-1])<=(n+1) && ((i==1)||s[i-2]!='X') && ((i+c[j-1])==(n+1) || s[i+c[j-1]-1]!='X') && !(cnt[i+c[j-1]-1]-cnt[i-1]))
				ans[i][j]=(dp[min(n+1,i+c[j-1]+1)][j+1]*dp2[max(0,i-2)][j-1])%MOD;
			ans[i][j]+=ans[i-1][j];
		}
	for (int i = 1; i <= n; ++i)
	{
		if(s[i-1]!='.')ANS.push_back(s[i-1]);
		else{
			ll f=0,f2=0;
			for (int j = 1; j <= k; ++j){
				f=(f+(ans[i][j]-ans[max(1,i-c[j-1]+1)-1][j]+MOD)%MOD)%MOD;
				f2=(f2+(dp[i+1][j]*dp2[i-1][j-1])%MOD)%MOD;
			}
			f2=(f2+(dp[i+1][k+1]*dp2[i-1][k])%MOD)%MOD;
			if(f==dp[1][1])ANS.push_back('X');
			else if(f2==dp[1][1])ANS.push_back('_');
			else ANS.push_back('?');
		}
	}
    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: 10 / 10