Submission #59004

#	Time	Username	Problem	Language	Result	Execution time	Memory
59004		tugushka	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1371 ms	183684 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
#define si( x ) scanf("%d", &x)
#define sll( x ) scanf("%lld", &x)
#define mp make_pair
#define pb push_back
#define N 200001
using namespace std;

typedef pair < int , int > pii;

vector < int > v;
string a;
int n, K;
int dp[N][101][2];
int cntb[N];
int b[N];
bool w[N];

int calc( int l, int r ){
	return cntb[r] - cntb[l-1];
}

bool rec( int now, int k, bool c ){
	if( now == 0 && k == -1 ) return 1;
	if( now < 0 ) return 0;
	if( dp[now][k][c] != -1 ) return dp[now][k][c];
	
	bool f = 0;
	if( (a[now] == '_' || a[now] == '.' ) && rec(now-1, k, 0) ) w[now] = f = 1;
	
	if( !c && k != -1 ){
		bool tmp = 0;
		if( calc( now-v[k]+1 , now ) == 0 )
			tmp |= rec( now-v[k], k-1, 1 );
		if( tmp ){
			f = 1, b[now-v[k]+1] = max( b[now-v[k]+1], v[k] );
		}
	}
	
	return dp[now][k][c] = f;
}

string solve_puzzle( string s, vector < int > c){
	a = " " + s;
	v = c;
	n = s.size(); K = c.size();
	memset( dp, -1, sizeof(dp) );
	for(int i = 1 ; i <= n ; i++)
		cntb[i] = cntb[i-1] + (a[i] == '_');
	
	rec( n, K-1, 0 );
	
	int cnt = 0;
	for(int i = 1 ; i <= n ; i++){
		cnt = max( cnt, b[i] );
		int d = 0;
		if( cnt ) d += 1;
		if( w[i] ) d += 2;
		
		if( d == 1 ) s[i-1] = 'X';
		if( d == 2 ) s[i-1] = '_';
		if( d == 3 ) s[i-1] = '?';
		
		cnt--;
	}
	
	return s;
}

/*
int main(){
	cin >> a >> K;
	vector < int > _v(K);
	for(int i = 0 ; i < K ; i++) si(_v[i]);
	
	cout << solve_puzzle( a, _v ) << endl;
}
*/

Compilation message (stderr)

paint.cpp: In function 'bool rec(int, int, bool)':
paint.cpp:41:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  return dp[now][k][c] = f;
         ~~~~~~~~~~~~~~^~~

• 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