Submission #1002318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002318		ZeroCool	Paint By Numbers (IOI16_paint)	C++14	100 / 100	127 ms	9700 KiB

paint

#include "paint.h"

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


string solve_puzzle(string s, vector<int> c) {
    int n = s.size();
	int k = c.size();
	s.insert(s.begin(), '.');
	c.insert(c.begin(), 0);
	
	bitset<105> dp1[n+2];
	bitset<105> dp2[n+2];
	int pref[n + 1];
	pref[0] = 0;
	for(int i = 1;i <= n;i++)pref[i] = pref[i-1] + (s[i] == '_');
	
	dp1[0][0] = 1;
	for(int i = 1;i <= n;i++){
		if(s[i] == 'X'){
			dp1[i] = 0;
			continue;
		}
		dp1[i] = dp1[i-1];
		for(int j = 1;j <= k;j++){
			bool b = (i > c[j]) && (pref[i - 1] - pref[i - c[j] - 1] == 0) && dp1[i - c[j] - 1][j - 1];
			if(b)dp1[i][j] = 1;
		}
	}
	dp2[n+1][k+1] = 1;
	for(int i = n;i >= 1;i--){
		if(s[i] == 'X'){
			dp2[i] = 0;
			continue;
		}
		dp2[i] = dp2[i+1];
		for(int j = 1;j <= k;j++){
			bool b = (i + c[j] <= n) && (pref[i + c[j]] - pref[i] == 0) && dp2[i + c[j] + 1][j + 1];
			if(b)dp2[i][j] = 1;
		}
	}
	int A[n+2];
	memset(A, 0, sizeof A);
	
	for(int j = 1;j <= k;j++){
		int ind = 1;
		for(int i = c[j];i <= n;i++, ind++){
			if(pref[i] - pref[ind - 1] > 0)continue;
			if(!dp1[ind-1][j-1])continue;
			if(!dp2[i+1][j+1])continue;
			A[ind]++;
			A[i + 1]--;
		}
	}
	for(int i =1;i <= n;i++)A[i] += A[i-1];
	string ans;
	for(int i = 1;i <= n;i++){
		if(s[i] != '.'){
			ans += s[i];
			continue;
		}
		bool w = 0, b = 0;
		for(int j = 0;j <= k;j++)w |= (dp1[i][j] && dp2[i][j+1]);
		b = A[i] > 0;
		if(w && b)ans += "?";
		else if(w)ans += "_";
		else ans += "X";
	}
	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