Submission #1219718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219718		boclobanchat	Paint By Numbers (IOI16_paint)	C++20	100 / 100	315 ms	331540 KiB

paint

#include"paint.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const long long mod=1e9+7;
int prefa[MAXN],prefb[MAXN];
long long dp[MAXN][105],dp2[MAXN][105];
string solve_puzzle(string s,vector<int> c)
{
	string t=s;
	int n=s.length(),m=c.size();
	dp[0][0]=dp2[n+1][m]=1,s=' '+s;
	for(int i=1;i<=n;i++)
	{
		prefa[i]=prefa[i-1]+(s[i]=='_');
		prefb[i]=prefb[i-1]+(s[i]=='X');
	}
	for(int i=1;i<=n+1;i++) for(int j=0;j<=m;j++) if(s[i]!='X')
	{
		dp[i][j]=dp[i-1][j];
		if(j&&i>c[j-1]&&prefa[i-1]==prefa[i-1-c[j-1]]) dp[i][j]=(dp[i][j]+dp[i-1-c[j-1]][j-1])%mod;
	}
	for(int i=n;i;i--) for(int j=0;j<=m;j++) if(s[i]!='X')
	{
		dp2[i][j]=dp2[i+1][j];
		if(j<m&&n-i+1>c[j]&&prefa[i]==prefa[i+c[j]]) dp2[i][j]=(dp2[i][j]+dp2[i+c[j]+1][j+1])%mod;
	}
	for(int i=1;i<=n;i++)
	{
		long long ans=0;
		for(int j=0;j<=m;j++) ans=(ans+dp[i][j]*dp2[i][j])%mod;
		if(ans==0) t[i-1]='X';
		else if(ans==dp[n+1][m]) t[i-1]='_';
		else t[i-1]='?';
	}
	return t;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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