Submission #435867

#	Time	Username	Problem	Language	Result	Execution time	Memory
435867		dutch	Paint By Numbers (IOI16_paint)	C++17	100 / 100	327 ms	42556 KiB

paint

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

void r(bool &a, bool b){ a = a || b; }

const int LIM = 2e5;

bool dp[2][LIM+2][101];
int n, k;

string solve_puzzle(string s, vector<int> c){
	n = s.size(), k = c.size();
	c.insert(c.begin(), 0);
	s.insert(s.begin(), 0);
 
	int a[n+1] = {0};

	for(int h=0; h<2; ++h){
		for(int i=0; i<=n; ++i) fill(dp[h][i], dp[h][i]+101, 0);
		reverse(c.begin()+1, c.end());
		reverse(s.begin()+1, s.end());

		for(int i=1; i<=n; ++i) a[i] = (s[i] == '_') + a[i-1];

		dp[h][0][0] = 1;
		for(int i=1; i<=n; ++i){
			if(s[i] != 'X') for(int j=0; j<=k; ++j) dp[h][i][j] = dp[h][i-1][j];
			for(int j=1; j<=k; ++j){
				if(i < c[j] || a[i] - a[i-c[j]]) continue;
				if(j < 2) r(dp[h][i][j], dp[h][i-c[j]][j-1]);
				if(j > 1) r(dp[h][i][j], i > c[j] && s[i-c[j]] != 'X' && dp[h][i-c[j]-1][j-1]);
			}
		}
	}
 
	bool possible[n+1];
	for(int i=1; i<n; ++i){
		possible[i] = 0;
		for(int j=0; j<=k; ++j){
			if(dp[1][i-1][j] && dp[0][n-i][k-j] && s[i] != 'X') possible[i] = 1;
		}
	}
	possible[n] = dp[1][n-1][k] && s[n] != 'X';
 
	vector<int> pre(n+2);
 
	s.push_back('.');
 
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=k; ++j){
			if(i < c[j] || a[i] - a[i-c[j]]) continue;
			if(dp[1][max(0, i-c[j]-1)][j-1] && s[i-c[j]] != 'X' && s[i+1] != 'X' && dp[0][max(0, n-i-1)][k-j]) ++pre[i-c[j]+1], --pre[i+1];
		}
	}
 
	string res(n, '?');
 
	for(int i=1; i<=n; ++i){
		pre[i] += pre[i-1];
		if(!pre[i]) res[i-1] = '_';
		if(!possible[i]) res[i-1] = 'X';
	}
 
	return res;
}

• 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