Submission #138888

#	Time	Username	Problem	Language	Result	Execution time	Memory
138888		bogdan10bos	Paint By Numbers (IOI16_paint)	C++14	32 / 100	3 ms	380 KiB

paint

/// Prosta
#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

int N, K;

vector<int> sum[2];

int getsum(int id, int st, int dr)
{
	if(st > dr)	return 0;
	if(st < 0)	return 0;
	if(st == 0)	return sum[id][dr];
	return sum[id][dr] - sum[id][st - 1];
}

void makesum(string s)
{
	sum[0].resize(N);
	sum[1].resize(N);
	for(int i = 0; i < N; i++)
	{
		if(i > 0)
		{
			sum[0][i] = sum[0][i - 1];
			sum[1][i] = sum[1][i - 1];
		}
		if(s[i] == '_')	sum[0][i]++;
		if(s[i] == 'X')	sum[1][i]++;
	}
}

void solve(string s, vector<int> c, vector< vector<int> > &can)
{
	makesum(s);
	can.resize(N);

	auto getcan = [&](int x, int y)
		{
		if(y >= 0 && x >= 0)	return can[x][y];
		if(y == 0)return 1;
		if(y > 0)	return 0;
		return 0;
		};

	for(int i = 0; i < N; i++)
	{
		can[i].resize(K + 1);
		can[i][0] = getsum(1, 0, i) == 0;
		for(int j = 1; j <= K; j++)
		{
			int l = c[j - 1];
			can[i][j] = 0;
			if(s[i] == '_')
				can[i][j] |= (i > 0 ? can[i - 1][j] : 0);
			else if(s[i] == 'X')
				can[i][j] |= ( (i >= l - 1 && getsum(0, i - l + 1, i) == 0 && getsum(1, i - l, i - l) == 0) ? getcan(i - l - 1, j - 1) : 0);
			else
			{
				can[i][j] |= (i > 0 ? can[i - 1][j] : 0);
				can[i][j] |= ( (i >= l - 1 && getsum(0, i - l + 1, i) == 0 && getsum(1, i - l, i - l) == 0) ? getcan(i - l - 1, j - 1) : 0);
			}
		}
	}
}

string solve_puzzle(string s, vector<int> c)
{
    N = s.size(), K = c.size();
    vector< vector<int> > pfx, sfx;
    solve(s, c, pfx);

    reverse(begin(s), end(s));
    reverse(begin(c), end(c));
    solve(s, c, sfx);

    reverse(begin(s), end(s));
    reverse(begin(c), end(c));

    makesum(s);
    string sol = "";

    vector<int> blk(N + 2), wht(N + 2);

    for(int i = 0; i < N; i++)
    {
    	bool white = false;
    	for(int j = 0; j <= K; j++)
    	{
    		bool left = false;
    		if(i == 0)	left = (j == 0 ? 1 : 0);
    		else	left = pfx[i - 1][j];

    		bool right = false;
    		if(i == N - 1)	right = (j == K ? 1 : 0);
    		else	right = sfx[N - i - 2][K - j];

    		if(left && right)
    		{
    			white = true;
    			break;
    		}
    	}
    	wht[i] = white;

    	for(int j = 0; j < K; j++)
    	{
    		if(i + c[j] > N)	continue;
    		bool left = false;
    		if(i == 0)	left = (j == 0 ? 1 : 0);
    		else if(i == 1)	left = (j == 0 ? pfx[i - 1][0] : 0);
    		else	left = (pfx[i - 2][j] & (s[i - 1] != 'X'));

    		i += c[j] - 1;
    		j++;
    		bool right = false;
    		if(i == N - 1)	right = (j == K ? 1 : 0);
    		else if(i == N - 2) right = (j == K ? sfx[N - i - 2][0] : 0);
    		else	right = (sfx[N - i - 3][K - j] & (s[i + 1] != 'X'));
    		j--;
    		i -= c[j] - 1;

    		if(!left || !right)	continue;
    		if(getsum(0, i, i + c[j] - 1) > 0)	continue;

    		blk[i]++;
    		blk[i + c[j]]--;
    	}
    }

    for(int i = 0; i < N; i++)
    {
    	if(i > 0)	blk[i] += blk[i - 1];
    	if(s[i] != '.')
    		sol.push_back(s[i]);
    	else if(wht[i] && blk[i] > 0)
    		sol.push_back('?');
    	else if(wht[i])
    		sol.push_back('_');
    	else
    		sol.push_back('X');
    }

    return sol;
}

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