Submission #867117

#	Time	Username	Problem	Language	Result	Execution time	Memory
867117		n1k	Paint By Numbers (IOI16_paint)	C++17	90 / 100	453 ms	524288 KiB

paint

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

#include <cstdlib>

using namespace std;


std::string solve_puzzle(std::string s, std::vector<int> c) {
	/*
	dp[i: 1..n][j: 1..k] -> if we can match s[1..i] with c[1..j]
	
	check  i: _ -> wenn dpl[i - 1][j] and dpr[i + 1][j + 1]
	check  i: X -> wenn dpl[i - lenl][j - 1] and dpr[i + 1][j + lenr]
	for i for j for start
	sum start = n
	*/
   	int n = s.size();
   	int k = c.size();
   	vector dpl(n + 5, vector(k + 5, vector<int>(2))), dpr(n + 5, vector(k + 5, vector<int>(2)));
	vector<int> free(n + 5), black(n + 5, 0), white(n + 5, 0);

	for(int i = 1; i <= n; i++){
		free[i] += free[i - 1] + (s[i - 1] == '_');
	}	
	// base case
	dpl[0][0][0] = 1;
	// dp[i][j][last] if we can place c[i] 

	for(int i = 0; i < n; i++){
		for(int j = 0; j <= k; j++){
			// place last == 0
			int end = i + c[j] - 1;
			if(end < n and free[end + 1] - free[i] == 0 and (end + 1 >= n or s[end + 1] != 'X')){
				if(j < k){
					dpl[end + 1][j + 1][1] |= dpl[i][j][0];
				}
			}
			// do not place if last == 0 or 1
			if(s[i] != 'X'){
				dpl[i + 1][j][0] |= dpl[i][j][0] | dpl[i][j][1];
			}
		}
	}
	dpr[n][k][0] = 1;
	for(int i = n; i >= 1; i--){
		for(int j = k; j >= 0; j--){
			// place last == 0
			int end = i - c[j - 1] + 1;
			if(end >= 1 and free[i] - free[end - 1] == 0 and (end - 2 < 0 or s[end - 2] != 'X')){
				if(j > 0){
					dpr[end - 1][j - 1][1] |= dpr[i][j][0];
				
					//ans
					if(dpl[end - 1][j - 1][0] & dpr[end - 1][j - 1][1]){
						black[end - 1]++;
						black[i + 1 - 1]--;
					}
				}
			}
			// do not place if last == 0 or 1
			if(s[i - 1] != 'X'){
				dpr[i - 1][j][0] |= dpr[i][j][0] | dpr[i][j][1];
				// ans
				white[i - 1] |= (dpl[i - 1][j][0] | dpl[i - 1][j][1]) & dpr[i - 1][j][0];
			}
		}
	}
	// XX...
	// ...XX
	// xxx..
	// .._xx
	for(int i = 0; i < n; i++){
		if(i > 0){
			black[i] += black[i - 1];
		}
		if(black[i] and white[i]){
			s[i] = '?';
		}else if(black[i]){
			s[i] = 'X';
		}else if(white[i]){
			s[i] = '_';
		}
	}

	return s;
}

/*
........
2 3 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: 0 / 10