Submission #388843

#	Time	Username	Problem	Language	Result	Execution time	Memory
388843		alireza_kaviani	Paint By Numbers (IOI16_paint)	C++11	100 / 100	557 ms	160848 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;

#define SZ(x)		int((x).size())
#define all(x)		(x).begin() , (x).end()
#define sep			' '

const int MAXN = 2e5 + 10;
const int MAXK = 110;

int n , k , dp[2][MAXK][MAXN] , mark[MAXN] , valid[MAXN];

void solve(int n , int k , string s , vector<int> c , int ind){
	if(ind == 1){
		reverse(all(s));
		reverse(all(c));
	}
	dp[ind][0][0] = 1;
	for(int i = 0 ; i <= k ; i++){
		int l = 0;
		for(int j = 1 ; j < n ; j++){
			if(s[j] == '_')	l = j;
			if(s[j] == '_' || s[j] == '.'){
				dp[ind][i][j] |= dp[ind][i][j - 1];
			}
			if((s[j] == 'X' || s[j] == '.') && i >= 1 && j - l >= c[i - 1]){
//				cout << ind << sep << i << sep << j << sep << endl;
				if(s[j - c[i - 1]] == 'X')	continue;
				dp[ind][i][j] |= dp[ind][i - 1][j - c[i - 1] - 1];
			}
		}
	}
	if(ind == 1){
		for(int i = 0 ; i <= k ; i++){
			reverse(dp[ind][i] , dp[ind][i] + n);
		}
	}
}

string solve_puzzle(string s, vector<int> c) {
	s = "__" + s + "__"; n = SZ(s); k = SZ(c);
	solve(n , k , s , c , 0);
	solve(n , k , s , c , 1);
/*	cout << n << endl;
	for(int i = 0 ; i <= k ; i++){
		for(int j = 0 ; j < n ; j++){
			cout << dp[0][i][j] << sep;
		}
		cout << endl;
	}
	for(int i = 0 ; i <= k ; i++){
		for(int j = 0 ; j < n ; j++){
			cout << dp[1][i][j] << sep;
		}
		cout << endl;
	}*/
	for(int i = 0 ; i <= k ; i++){
		for(int j = 2 ; j + 2 < n ; j++){
			if(s[j] == 'X')	continue;
			if(dp[0][i][j - 1] && dp[1][k - i][j + 1]){
				mark[j] |= 1;
			}
		}
	}
	for(int i = 0 ; i < k ; i++){
		int l = 1;
		fill(valid , valid + MAXN , 0);
		for(int j = 2 ; j + 2 < n ; j++){
			if(s[j] == '_'){
				l = j;
				continue;
			}
			if(j - l < c[i] || s[j + 1] == 'X' || s[j - c[i]] == 'X')	continue;
			if(dp[0][i][j - c[i] - 1] && dp[1][k - i - 1][j + 2]){
				valid[j] = 1;
			}
		}
		int sum = 0;
		for(int j = n - 1 ; j >= 0 ; j--){
			sum += valid[j];
			if(j + c[i] < n)	sum -= valid[j + c[i]];
			if(sum)	mark[j] |= 2;
		}
	}
	for(int i = 0 ; i < n ; i++){
		if(s[i] == '.'){
			if(mark[i] == 1)	s[i] = '_';
			if(mark[i] == 2)	s[i] = 'X';
			if(mark[i] == 3)	s[i] = '?';
		}
	}
	return s.substr(2 , n - 4);
}

• 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