Submission #137417

#	Time	Username	Problem	Language	Result	Execution time	Memory
137417		mirbek01	Paint By Numbers (IOI16_paint)	C++11	100 / 100	932 ms	240960 KiB

paint

#include "paint.h"
//#include "grader.cpp"
 
#include <cstdlib>
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e5 + 3;

int n, m;
int pf[3][N], dp[2][202][N], pfX[N], sfX[N], f[202][N];

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

int Get(int l, int r, int tp){
	if(l > r) return 0;
	return f[tp][r] - f[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] ++, pfX[i] = i;
		else 
			pfX[i] = pfX[i - 1]; 
		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];
	}
	
	sfX[n + 1] = n + 1;
	
	for(int i = n; i >= 1; i --){
		if(s[i] == 'X')
			sfX[i] = i;
		else 
			sfX[i] = sfX[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)
			dp[0][0][i] = 1;
	
	for(int i = 1; i < m; i ++){
		vector <int> pf(n + 1, 0);
		for(int j = 1; j <= n; j ++)
			pf[j] = pf[j - 1] + dp[0][i - 1][j];
		for(int j = c[i] + 1; j <= n; j ++){
			if(s[j - c[i]] == 'X' || s[j + 1] == 'X') continue;
			if(get(j - c[i] + 1, j, 1) > 0) continue;
			int sum = pf[j - c[i] - 1] - pf[ max(0, pfX[j - c[i]] - 1) ];
			if(sum <= 0) continue;
			dp[0][i][j] = 1;
		}
	}
	
	for(int i = n; i >= c[m - 1]; i --){
		if(get(i - c[m - 1] + 1, i, 1) == 0 && get(i + 1, n, 0) == 0)
			dp[1][m - 1][i] = 1;
	}
	
	for(int i = m - 2; i >= 0; i --){
		vector <int> sf(n + 2, 0);
		for(int j = n; j >= 1; j --)
			sf[j] = sf[j + 1] + dp[1][i + 1][j];
		for(int j = c[i]; j <= n; j ++){
			if((j + 1 <= n && s[j + 1] == 'X') || s[j - c[i]] == 'X') continue;
			if(get(j - c[i] + 1, j, 1) > 0) continue;
			if(j + c[i + 1] + 1 > n) continue;
			int sum = sf[j + c[i + 1] + 1] - sf[ min(sfX[j + 1] + c[i + 1] + 1, n + 1) ];
			if(sum <= 0) continue;
			dp[1][i][j] = 1;
		}
	}
	
	for(int i = 0; i < m; i ++)
		for(int j = 1; j <= n; j ++)
			if(dp[0][i][j] && !dp[1][i][j])
				dp[0][i][j] = 0;
	for(int i = 0; i < m; i ++)
		for(int j = 1; j <= n; j ++)
			f[i][j] = f[i][j - 1] + dp[0][i][j];
	string ans;
    
    for(int i = 1; i <= n; i ++){
		if(s[i] != '.'){
			ans += s[i];
			continue;
		}
		int canX = 0, can_ = 0;
		for(int j = 0; j < m; j ++){
			if(j == 0){
				if(get(1, i - 1, 0) == 0 && i + c[j] <= n && Get(i + c[j], min(sfX[i + 1] + c[j], n), j))
					can_ = 1;
			} else {
				if(Get(max(pfX[i - 1], 1), i - 1, j - 1) && i + c[j] <= n && Get(i + c[j], min(sfX[i + 1] + c[j], n), j))
					can_ = 1;
			}
			if(Get(i, min(i + c[j] - 1, n), j))
				canX = 1;
		}
		if(Get(pfX[i - 1], i - 1, m - 1) && get(i + 1, n, 0) == 0)
			can_ = 1;
		if(can_ && canX)
			ans += '?';
		else if(can_)
			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