Submission #1275269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275269		Petrix	Paint By Numbers (IOI16_paint)	C++20	32 / 100	1 ms	348 KiB

paint

#include <iostream>
#include "paint.h"
#include <vector>
using namespace std;

#define MOD 1000000007
int dp[200001][101];
int dp1[200001][101];
int pref1[200001];
int pref2[200001];

string solve_puzzle(string s,vector<int> c){
    string fina=s;int n=s.size(),m=c.size(),i,j,rasp;
	dp[0][0]=dp1[n+1][m]=1;s=" "+s;
	for(i=1;i<=n;i++){
		pref1[i]=pref1[i-1];
		if(s[i]=='_') pref1[i]++;
		pref2[i]=pref2[i-1];
		if(s[i]=='X') pref2[i]++;
	}
	for(i=1;i<=n+1;i++){
        for(j=0;j<=m;j++){
            if(s[i]!='X'){
                dp[i][j]=dp[i-1][j];
                if(j && i>c[j-1] && pref1[i-1]==pref1[i-1-c[j-1]]){
                    dp[i][j]+=dp[i-c[j-1]-1][j-1];dp[i][j]%=MOD;
                }
            }
        }
    }
    for(i=n;i;i--){
        for(j=0;j<=m;j++){
            if(s[i]!='X'){
                dp1[i][j]=dp1[i+1][j];
                if(j<m && n-i+1>c[j] && pref1[i]==pref1[i+c[j]]){
                    dp1[i][j]+=dp1[i+c[j]+1][j+1];dp1[i][j]%=MOD;
                }
            }
        }
    }
    for(i=1;i<=n;i++){
		rasp=0;
		for(j=0;j<=m;j++)
            rasp=(rasp+dp[i][j]*dp1[i][j])%MOD;
		if(!rasp) fina[i-1]='X';
		else if(rasp==dp[n+1][m]) fina[i-1]='_';
		else fina[i-1]='?';
	}
	return fina;
}

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: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10