Submission #570062

#	Time	Username	Problem	Language	Result	Execution time	Memory
570062		franfill	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	340 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;

int n, k;
string s;
vector < int > c;
vector < int > cnt_, cntX;
vector < bool > can_, canX;

vector < vector < int > > memo;

bool has_(int l, int r)
{
	r = min(r, n);
	return cnt_[r] > cnt_[l];
}

bool hasX(int l, int r)
{
	r = min(r, n);
	return cntX[r] > cntX[l];
}

void setX(int l, int r)
{
	for (int i = l; i < r; i++) canX[i] = true;
}

void set_(int l, int r)
{
	for (int i = l; i < r; i++) can_[i] = true;
}

bool verifica(int i, int j)
{
	if (j == k) if (!hasX(i, n))
	{
		set_(i, n);
		return 1;
	}
	else return 0;
	if (i >= n) return 0;
	if (memo[i][j] != -1) return memo[i][j];
	bool ok = false;
	if (i + c[j] < n && !has_(i, i+c[j]) && s[i+c[j]] != 'X')
	{
		if (verifica(i+c[j]+1, j+1))
		{
			//cerr << i << ", " << j << " -> " << i+c[j]+1 << " " << j+1 << "(X)\n";
			setX(i, i+c[j]);	
			if (i + c[j] < n) can_[i+c[j]] = true;
			ok = true;
		}
	}
	if (s[i] != 'X')
	{
		if (verifica(i+1, j))
		{
			//cerr << i << ", " << j << " -> " << i+1 << " " << j << "(_)\n";
			can_[i] = true;
			ok = true;
		}
	}
	//cerr << i << " " << j << " " << ok << "\n";
	return memo[i][j] = ok;
}

std::string solve_puzzle(std::string ss, std::vector<int> cc) 
{
	s = ss;
	s += "_";
	c = cc;
	n = s.size();	
	k = c.size();
	memo.resize(n, vector < int > (k, -1));

	cnt_.resize(n+1,0);
	cntX.resize(n+1,0);
	can_.resize(n, 0);
	canX.resize(n, 0);
	for (int i = 1; i < n; i++)
	{
		cnt_[i] = cnt_[i-1] + (s[i-1] == '_');
		cntX[i] = cntX[i-1] + (s[i-1] == 'X');
	}
	string ans = "";
	for (int i = 0; i < n; i++)
	{
		verifica(i, 0);
		if (s[i] == 'X') break;
	}
	for (int i = 0; i < n-1; i++)
	{
		assert(canX[i] || can_[i]);
		if (!canX[i]) ans += "_";
		else if (!can_[i]) ans += "X";
		else ans += "?";
	}
    return ans; 
}

Compilation message (stderr)

paint.cpp: In function 'bool verifica(int, int)':
paint.cpp:37:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   37 |  if (j == k) if (!hasX(i, n))
      |     ^
paint.cpp:66:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   66 |  return memo[i][j] = ok;

• 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