Submission #136788

#	Time	Username	Problem	Language	Result	Execution time	Memory
136788		mirbek01	Paint By Numbers (IOI16_paint)	C++11	7 / 100	4 ms	376 KiB

paint

#include "paint.h"
//#include "grader.cpp"

#include <cstdlib>
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 3;

int pf[3][N], n, m;
int dp[202][N], pref[N], f[3][N];

int get(int l, int r, int tp){
	if(l > r) return 0;
	return pf[tp][r] - pf[tp][l - 1];
}

string solve_puzzle(string s, vector<int> c) {
	n = (int)s.size();
	m = (int)c.size();
	s = ' ' + s;
	for(int i = 1; i <= n; i ++){
		if(s[i] == 'X')
			pf[0][i] ++;
		if(s[i] == '_')
			pf[1][i] ++;
		if(s[i] == '.')
			pf[2][i] ++;
		pf[0][i] += pf[0][i - 1];
		pf[1][i] += pf[1][i - 1];
		pf[2][i] += pf[2][i - 1];
	} 
	
	for(int i = c[0]; i <= n; i ++){
		if(get(i - c[0] + 1, i, 1) == 0 && get(1, i - c[0], 0) == 0 && (m != 1 || get(i + 1, n, 0) == 0))
			dp[0][i] = 1;
	}
	
	for(int i = 1; i < m; i ++){
		vector <int> pf(n + 1, 0), lastX(n + 1, 0);
		for(int j = 1; j <= n; j ++){
			pf[j] = pf[j - 1] + dp[i - 1][j];
		}
		for(int j = c[i] + 1; j <= n; j ++){
			if(get(j - c[i] + 1, j, 1) == 0 && get(j - c[i], j - c[i], 0) == 0){
				int sum = pf[j - c[i] - 1] - pf[lastX[j - c[i] - 1]];
				if(sum && (i != m - 1 || get(j + 1, n, 0) == 0)) dp[i][j] = 1;
			}
			if(s[j] == 'X')
				lastX[j] = j;
			lastX[j] = max(lastX[j], lastX[j - 1]); 
		}
	}
	
	int sum = c[m - 1];
	for(int i = m - 2; i >= 0; i --){
		vector <int> pf(n + 2, 0);
		for(int j = n; j >= 1; j --){
			pf[j] = pf[j + 1] + dp[i + 1][j];
		}
		for(int j = 1; j <= n; j ++){
			if(dp[i][j] && (j + sum >= n || !pf[j + sum]))
				dp[i][j] = 0;
		}
		sum += c[i];
	}
	
	for(int i = 0; i < m; i ++){
		int cnt = 0;
		for(int j = 1; j <= n; j ++){
			if(dp[i][j])
				cnt ++;
			f[0][j] = 0;
 		}
		for(int j = 1; j <= n; j ++){
			if(dp[i][j]){
				f[0][j - c[i] + 1] ++;
				f[0][j + 1] --;
			}
		}
		for(int j = 1; j <= n; j ++){
			f[0][j] += f[0][j - 1];
			if(f[0][j] != cnt)
				f[1][j] ++;
			if(f[0][j])
				f[2][j] ++;
			if(f[0][j] == cnt)
				f[1][j] += -1e9;
		}
	}
	
	string ans;
	
	for(int i = 1; i <= n; i ++){
		if(s[i] == '.'){
			int canX = 0, can_ = 0;
			if(f[2][i] > 0)
				canX = 1;
			if(f[1][i] > 0)
				can_ = 1;
			if(canX && can_)
				ans += '?';
			else if(canX)
				ans += 'X';
			else 
				ans += '_';
		} else 
			ans += s[i];
	}
		
    return ans;
}
/***
.X........
1 3 

....._X...
2 2 2
**/

• Subtask 1: 7 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10