Submission #584199

#	Time	Username	Problem	Language	Result	Execution time	Memory
584199		amunduzbaev	Paint By Numbers (IOI16_paint)	C++17	100 / 100	331 ms	332656 KiB

paint

#include "paint.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

const int N = 2e5 + 5;
const int K = 105;
int dp[N][K][2], pref[N][2];
int tp[N][K][2], is[N];

string solve_puzzle(string s, vector<int> c) {
	int n = s.size(), k = c.size();
	c.insert(c.begin(), n + 1);
	c.push_back(n + 1);
	s = "#" + s;
	for(int i=1;i<=n;i++){
		pref[i][0] = pref[i-1][0];
		pref[i][1] = pref[i-1][1];
		if(s[i] != '.'){
			pref[i][s[i] == 'X']++;
		}
	}
	
	dp[0][0][0] = 1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			if(s[i] != 'X'){
				dp[i][j][0] = dp[i-1][j][1] | dp[i-1][j][0];
			}
			if(i >= c[j] && pref[i][0] - pref[i - c[j]][0] == 0){
				dp[i][j][1] = dp[i - c[j]][j - 1][0];
			}
		}
	}
	
	tp[n + 1][k + 1][0] = 1;
	for(int i=n;i>0;i--){
		for(int j=k + 1;j>0;j--){
			if(s[i] != 'X'){
				tp[i][j][0] = tp[i+1][j][1] | tp[i+1][j][0];
			}
			if(i + c[j] <= n + 1 && pref[i + c[j] - 1][0] - pref[i - 1][0] == 0){
				tp[i][j][1] = tp[i + c[j]][j + 1][0];
			}
		}
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			if(dp[i][j][1] && tp[i + 1][j + 1][0]){
				is[i - c[j] + 1]++;
				is[i + 1]--;
			}
		}
	}
	
	//~ for(int j=1;j<=k;j++){
		//~ for(int i=1;i<=n;i++){
			//~ cout<<(dp[i][j][1] && tp[i + 1][j + 1][0])<<" ";
		//~ } cout<<"\n";
	//~ }
	
	for(int i=1;i<=n;i++){
		is[i] += is[i-1];
	}
	
	string res;
	for(int i=1;i<=n;i++){
		bool ok = 0;
		for(int j=0;j<=k;j++){
			if(dp[i][j][0] && tp[i][j + 1][0]){
				ok = 1;
			}
		}
		
		if(ok && is[i]){
			res.push_back('?');
		} else if(is[i]){
			res.push_back('X');
		} else if(ok) {
			res.push_back('_');
		} else assert(false);
	}
	
	return res;
}

/*

........
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: 10 / 10