Submission #50881

#	Time	Username	Problem	Language	Result	Execution time	Memory
50881		MatheusLealV	Paint By Numbers (IOI16_paint)	C++17	59 / 100	12 ms	7804 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

int L[200050][120], R[200050][120], n, k, white[200050], black[200050], qtd[200050];

int global[200050], ini[200050], fim[200050];

char ans[200050];

vector<int> pos[120], pertence[200050];

int qblack(int l, int r) {
	if(l > r) return 0;
	return black[r] - (l > 0 ? black[l - 1] : 0);
}

int qwhite(int l, int r){
	if(l > r) return 0;
	return white[r] - (l > 0 ? white[l - 1] : 0);	
}

string solve_puzzle(string s, vector<int> c)
{
	n = s.size(), k = c.size();

	for(int i = 0; i < n; i++)
	{
		white[i] = (i > 0 ? white[i - 1] : 0);

		black[i] = (i > 0 ? black[i - 1] : 0);

		if(s[i] == '_') white[i] ++;

		if(s[i] == 'X') black[i] ++;
	}

	memset(fim, 0x3f3f3f3f, sizeof fim);

	memset(ini, -1, sizeof ini);

	for(int q = 0; q < k; q++)
	{
		for(int i = 0; i < n; i++)
		{
			int ini = i - c[q] + 1;

			if(ini < 0) continue;

			bool tem = ( !q and (qblack(0, ini - 1) == 0) ), impossivel = false;

			if(q == k - 1 and qblack(i + 1, n - 1) > 0)  impossivel = true;

			for(int j = 0; j < ini - 1; j++)
				if(q > 0 and !tem and L[j][q - 1] and qblack(j + 1, ini - 1) == 0 ) tem = true;

			if(tem and qwhite(ini, i) == 0 and !impossivel) L[i][q] = true;

			//cout<<"LLLL "<<i<<" "<<q<<" "<<L[i][q]<<"\n";
		}
	}

	for(int q = k - 1; q >= 0; q--)
	{
		for(int i = n - 1; i >= 0; i--)
		{
			int fim = i + c[q] - 1;

			if(fim >= n) continue;

			bool tem = ((q == (k - 1)) and (qblack(fim + 1, n - 1) == 0)), impossivel = false;

			if(q == 0 and qblack(0, i - 1) > 0) impossivel = true;

			for(int j = n - 1; j > fim + 1; j--)
				if(q < k - 1 and !tem and R[j][q + 1] and qblack(fim + 1, j - 1) == 0) tem = true;

			if(tem and qwhite(i, fim) == 0 and !impossivel) R[i][q] = true;

			//cout<<"RRR "<<i<<" "<<q<<" "<<R[i][q]<<"\n";
		}
	}

	for(int q = 0; q < k; q++)
		for(int i = 0; i < n; i++)
			if(i - c[q] + 1 >= 0 and L[i][q] and R[i - c[q] + 1][q]) pos[q].push_back(i - c[q] + 1);

	for(int i = 0; i < n; i++)
	{
		for(int q = 0; q < k; q++)
		{
			if(i - c[q] + 1 >= 0 and L[i][q] and R[i - c[q] + 1][q] and s[i - c[q] + 1] == 'X')
			{
				ini[i - c[q] + 1] = max(ini[i], i - c[q] + 1);

				fim[i - c[q] + 1] = min(fim[i], i);
			}
		}
	}

	for(int i = 0; i < n; i++)
	{
		if(s[i] == 'X' and ini[i] != -1)
			for(int p = ini[i]; p <= fim[i]; p++) ans[p] = 'X';
	}

	for(int q = 0; q < k; q++)
	{
		memset(qtd, 0, sizeof qtd);

		for(auto i: pos[q])
		{
			qtd[i] ++;

			qtd[i + c[q]] --;

			global[i] ++;

			global[i + c[q]] --;
		}

		for(int i = 1; i < n; i++) qtd[i] += qtd[i - 1];

		for(int i = 0; i < n; i++)
			if(qtd[i] == pos[q].size())ans[i] = 'X';
	}

	string resp;

	for(int i = 1; i < n; i++) global[i] += global[i - 1];

	for(int i = 0; i < n; i++)
	{
		char p = '?';

		if(s[i] != '.') p = s[i];

		else if(!global[i] and ans[i] != 'X') p = '_';

		else if(ans[i] == 'X') p = 'X';

		resp.push_back(p);
	}

	return resp;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:127:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(qtd[i] == pos[q].size())ans[i] = 'X';
       ~~~~~~~^~~~~~~~~~~~~~~~

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