Submission #266924

#	Time	Username	Problem	Language	Result	Execution time	Memory
266924		amiratou	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1520 ms	244420 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9+7;
const int MAXN=(int)2e5+3,MAXK=103;
typedef long long ll;
int dp[MAXN][MAXK],dp2[MAXN][MAXK],ans[MAXN][MAXK];
int cnt[MAXN];
string ANS;
void mod(int& a){
	if(a>=MOD)a%=MOD;
}

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+c[j-1]][j+1],mod(dp[i][j]);
				else dp[i][j]+=dp[i+c[j-1]+1][j+1],mod(dp[i][j]);
			}
			if(s[i-1]!='X')dp[i][j]+=dp[i+1][j],mod(dp[i][j]);
		}
		if(s[i-1]!='X')dp[i][k+1]+=dp[i+1][k+1],mod(dp[i][k+1]);
	}
	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-c[j-1]][j-1],mod(dp2[i][j]);
				else dp2[i][j]+=dp2[i-c[j-1]-1][j-1],mod(dp2[i][j]);
			}	
			if(s[i-1]!='X')dp2[i][j]+=dp2[i-1][j],mod(dp2[i][j]);
		}
		if(s[i-1]!='X')dp2[i][0]+=dp2[i-1][0],mod(dp2[i][0]);
	}
	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]=((ll)dp[min(n+1,i+c[j-1]+1)][j+1]*(ll)dp2[max(0,i-2)][j-1])%MOD;
			ans[i][j]+=ans[i-1][j],mod(ans[i][j]);
		}
	for (int i = 1; i <= n; ++i){
		if(s[i-1]!='.')ANS.push_back(s[i-1]);
		else{
			int f=0,f2=0;
			for (int j = 1; j <= k; ++j){
				f+=(ans[i][j]-ans[max(1,i-c[j-1]+1)-1][j]+MOD)%MOD;
				f2+=((ll)dp[i+1][j]*(ll)dp2[i-1][j-1])%MOD;
				mod(f),mod(f2);
			}
			f2+=((ll)dp[i+1][k+1]*(ll)dp2[i-1][k])%MOD,mod(f2);
			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