Submission #418616

#	Time	Username	Problem	Language	Result	Execution time	Memory
418616		CaroLinda	Paint By Numbers (IOI16_paint)	C++14	100 / 100	487 ms	519888 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define ll long long

const int MAXN = 2e5+10 ;
const int MAXK = 110 ;
const ll MOD = 1e9+7 ;

using namespace std ;

int N , K ;
int sv_black[MAXN] , sv_white[MAXN] ;
string s ;
vector<int> c ;
ll dp[MAXN][MAXK] , dpPref[MAXN][MAXK], dpSuf[MAXN][MAXK] ;

int getBlack(int l, int r ) { return sv_black[r] - sv_black[l-1] ; }
int getWhite(int l, int r ) { return sv_white[r] - sv_white[l-1] ; }

void calc()
{
	dp[0][0] = 1 ;

	for(int i = 1 ; i <= N ; i++ )
	{
		dp[i][0] = (getBlack(1,i) == 0 ) ;

		for(int j = 1 ; j <= K ; j++ )
		{
			dp[i][j] = dp[i-1][j] * ( s[i] != 'X' ) ;
		
			if( i-c[j] < 0 || getWhite(i-c[j]+1, i) ) continue ;
			if( i-c[j] > 0 && s[i-c[j]] == 'X' ) continue ;

			if( i-c[j] == 0 ) dp[i][j] += (j == 1 ) ;
			else dp[i][j] += dp[i-c[j]-1][j-1] ;

			if( dp[i][j] >= MOD ) dp[i][j] -= MOD ;
		}
	}
}

void calc_sv()
{
	for(int i = 1 ; i <= N ; i++ )
	{
		sv_black[i] = ( s[i] == 'X' ) ;
		sv_white[i] = ( s[i] == '_' ) ;

		sv_black[i] += sv_black[i-1] ;
		sv_white[i] += sv_white[i-1] ;
	}

}

string solve_puzzle(string _s, vector<int> _c) 
{
	s = _s ;
	c = _c ;

	N = sz(s) ;	
	K = sz(c) ;

	c.insert(c.begin() , 0 ) ;
	c.push_back(0) ;
	s.insert( s.begin() , '.' ) ;
	s.push_back('.') ;

	calc_sv() ;
	calc() ;

	for(int i = 0 ; i <= N ; i++ )
		for(int j = 0 ; j <= K ; j++ )
		{
			dpPref[i][j] = dp[i][j] ;
			dp[i][j] = 0 ;
		}

	reverse( all(c) ) ;
	reverse( all(s) ) ;

	calc_sv() ;
	calc() ;

	for(int i = 0 , j = N+1 ; i <= N ; i++ , j-- )
		for(int a = 0 , b = K+1 ; a <= K ; a++ , b-- )
			dpSuf[j][b] = dp[i][a] ;

	reverse( all(c) ) ;
	reverse( all(s) ) ;
	
	for(int i = 1 ; i <= N ; i++ )
	{
		if( s[i] == 'X' ) continue ;

		ll qtd_as_white = 0 , temp ;

		for(int j = 0 ; j <= K ; j++ )
		{
			temp = dpPref[i-1][j] * dpSuf[i+1][j+1] ;
			temp %= MOD ;

			qtd_as_white += temp ;							
			if( qtd_as_white >= MOD ) qtd_as_white -= MOD ;
		}			

		if( qtd_as_white == dpPref[N][K] ) s[i] = '_' ;
		else if( qtd_as_white == 0 ) s[i] = 'X' ;
		else s[i] = '?' ; 

	}

	string ans ;
	for(int i = 1 ; i<= N ; i++ ) ans.push_back(s[i] ) ;

	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